ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 11

Тема: «Программирование рекурсивных алгоритмов»

Цель: изучить правила составления рекурсивных алгоритмов, научиться решать задачи с помощью рекурсии.

 

Ход работы

 

Теоретические обоснования

Рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию). 

Типичными рекурсивными задачами являются задачи: нахождения n!, числа Фибоначчи. Такие задачи решаются и с использованием циклов, то есть итеративно. Вообще говоря, всё то, что решается итеративно можно решить рекурсивно, то есть с использованием рекурсивной функции. Всё решение сводится к решению основного или, как ещё его называют, базового (граничного) случая. Существует такое понятие как шаг рекурсии или рекурсивный вызов. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.

Обращение к рекурсивной подпрограмме ничем не отличается от вызова любой другой подпрограммы. При этом при каждом новом рекурсивном обращении в памяти создаётся новая копия подпрограммы со всеми локальными переменными. Такие копии будут порождаться до выхода на граничное условие. Очевидно, в случае отсутствия граничного условия, неограниченный рост числа таких копий приведёт к аварийному завершению программы за счёт переполнения стека.

Порождение все новых копий рекурсивной подпрограммы до выхода на граничное условие называется рекурсивным спуском. Максимальное количество копий рекурсивной подпрограммы, которое одновременно может находиться в памяти компьютера, называется глубиной рекурсии. Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным подъёмом.

 

Типичная рекурсивная процедура имеет вид:

тип Rec (int n)

{

  действие на входе рекурсию;

  if (проверка условия)

Rec(n-1);

  else   действия на выходе из рекурсии;

}

 

ВЫВОД

Для реализации рекурсивной подпрограммы необходимо:

1)      Знать граничное (базовое) решение

2)      Создать формулу, по которой будет вычисляться значение на каждом шаге рекурсии.

 

ПРИМЕР 1. Разработаем программу, в которой объявлена рекурсивная функция, вычисляющая n!

Для вычисления факториала знаем, что:

1)      1! = 1 и 0! = 1 – граничное решение

2)      Формула для расчета факториала с помощью рекурсивной функции:

n!=n*(n-1)!

Для функции fact() был объявлен тип данных unsigned long int, так как значение факториала возрастает очень быстро, например уже 10! = 3 628 800. Если не хватит размера типа данных, то в результате мы получим совсем не правильное значение.

Обратите внимание на выделенные строки кода, строки 18, 20, 21 — это рекурсивное решение n!. Строки 18, 20, являются базовым решением рекурсивной функции, то есть, как только значение в переменной f  будет равно 1 или 0 (так как мы знаем, что 1! = 1 и 0! = 1), прекратятся рекурсивные вызовы, и начнут возвращаться значения, для каждого рекурсивного вызова. Когда вернётся значение для первого рекурсивного вызова, программа вернёт значение вычисляемого факториала. В строке 21 функция fact() вызывает саму себя, но уже её аргумент на единицу меньше. Аргумент каждый раз уменьшается, чтобы достичь частного решения.

Рассмотрим, как работает рекурсивная функция на примере вычисления факториала. Пусть необходимо вычислить пять факториал. Программа сделает четыре рекурсивных обращения, на пятом обращении будет найден базовый случай. И как только  программа получит решение базового случая, она порешает предыдущие шаги и выведет общий результат.

На рисунке 1 видно всего четыре шага потому, что на пятом шаге было найдено частное решение, что  в итоге вернуло конечное решение, т. е. 120. На рисунке 2 показана схема рекурсивного вычисления 5!. В схеме хорошо видно, что первый результат возвращается, когда достигнуто частное решение, но никак не сразу, после каждого рекурсивного вызова.

 

Итак, чтобы найти 5! нужно знать 4! и умножить его на 5; 4! = 4 * 3! и так далее. Согласно схеме, изображённой на рисунке 2, вычисление сведётся к нахождению частного случая, то есть 1!, после чего по очереди будут возвращаться значения каждому рекурсивному вызову. Последний рекурсивный вызов вернёт значение 5!.

 

Переделаем программу нахождения факториала так, чтобы получить таблицу факториалов. Для этого объявим цикл for, в котором будем вызывать рекурсивную функцию.

 

 

ПРИМЕР 2. Рассмотрим ещё одну типичную задачу — нахождение чисел Фибоначчи, используя рекурсию.

1)      Нулевое и первое значения должны быть заданы, их значения равны единице. Это граничные условия. Т.е. при n=1 или n=2 числа Фибоначчи равны 1.

2)      Числа Фибоначчи составляют последовательность, очередной элемент которой вычисляется по двум предыдущим значениям:

Fn=Fn-1 + Fn-2

Это формула для реализации рекурсии.

 

Далее приведен код рекурсивного решения такой задачи. Вводим порядковый номер числа из ряда Фибоначчи, и программа выдает число Фибоначчи с введенным номером.

 

 

Изменим программу для решения такой задачи:

Вводим порядковый номер числа из ряда Фибоначчи, и программа найдёт все числа из ряда Фибоначчи, порядковые номера которых меньше либо равны введённого.

 

ПРИМЕР 3. Вычислить сумму элементов линейного массива.

 

При решении задачи используем следующие соображения:

1)      сумма массива равна нулю, если количество элементов равно нулю

2)      сумма массива равна сумме всех предыдущих элементов плюс последний, если количество элементов не равно нулю:

s=s+a[n]

 

 

ПРИМЕР 4. Функция , для вычисления биномиального коэффициента  по следующей формуле  при  является рекурсивной.

           

int C(int m, int n)

            {

    int f;

    if (m==0||m==n) f=1;

else f=C(m, n-1)+C(m-1, n-1);

    return f;

  }

 

ПРИМЕР 5. Вывести натуральные числа от n до 1.

void vivod(int n)

{

            cout<<"n="; cin>>n;

            if (n==0)

            cout<<"\n"<<"Последовательность в обратном порядке:"<<"\n";

            else

                        {

                                   vivod(n);

                                    if (n!=0) cout<<n;

                                               else exit;

                        }

}

 

Решить самостоятельно:

Составить программу для решения каждой задачи, используя рекурсивную подпрограмму.

1.    Вывести факториалы чисел до введенного N.

2.    Вывести факториалы чисел до введенного N.

3.    Вычислить N-ое число Фибоначчи.

4.    Вычислить последовательность чисел Фибоначчи до введенного N.

5.    Посчитать сумму элементов одномерного массива двумя способами: с помощью цикла и с помощью рекурсии. Вывести оба результата.

6.    Вычислить хn, где x – целое число, а n – целое неотрицательное число. Воспользоваться тем, что хn=x* хn-1

7.    Вычислить  с помощью одной рекурсивной функции. В рекурсивной подпрограмме проверить является ли  отрицательным и равным нулю. Воспользоваться тем, что

8.    Напечатать квадраты всех целых чисел от нуля до введенного натурального http://www.ctc.msiu.ru/materials/Book/img1.gif.

9.    Напечатать  двоичное  представление  натурального числа.

10.     Найти n-ый члена арифметической прогрессии.

 - формула n-го члена арифметической прогрессии.

11.     Найти сумму членов арифметической прогрессии