Страницы

Уроки 35, 36 Рекурсия


В жизни Вам не раз приходилось сталкиваться с рекурсией. Вспомните хотя бы стихотворение "У попа была собака" или “10 негритят пошли купаться в море…”

Рекурсией  называется ситуация, когда процедура или функция вызывает сама себя.

Пример рекурсии: Если у вас жирное пятно на платье, не переживайте. Пятна от масла убираются бензином. Пятно от бензина раствором щёлочи. Щелочь убирается эссенцией. След от эссенции потрите маслом. Ну, а как убрать пятна от масла, вы уже знаете!

Конструкция рекурсивной процедуры имеет вид:

Procedure Rec (t: Integer) ;
Begin
действия на входе в рекурсию;
If  проверка условия
Then Rec (t+1) ;
действия на выходе из рекурсии;
End;

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


Задание 1. Написать подпрограмму для вычисления факториала числа.
Факториал числа N обозначается N!.
N!=1*2*3*...*N.
Факториал 1 равен 1,   2!=1·2=1!·2,   3!=1·2·3=2!·3 … n!=(n-1)!·n.

Реализуем  вспомогательную программу для вычисления факториала числа с помощью процедуры:

Procedure Fact(N:integer; Var F:int64);
Begin
        If N<=1
        Then F:=1
        Else Begin Fact(N-1, F); F:=F*N End
End;

Реализуем  вспомогательную программу для вычисления факториала числа с помощью функции:

Function Fact(N:integer):int64;
  Begin
      If N<=1
      Then Fact:=1
      Else Fact:=Fact(N-1)*N
  End;

Рассмотрим выполнение рекурсивной функции при n=5, т.е.  вычислим 5!


Из рисунка видно, что рекурсия связана с многократными вызовами функции, а это несколько менее эффективно при выполнении по сравнению с использованием цикла. К тому же требует больше памяти. Однако рекурсивные версии программ, как правило, гораздо короче и нагляднее, не требуют наличия цикла и параметра цикла.


      Тесты      Посмотреть решение       

Экспериментальный раздел


1. Вычислить 5!+6!-11!

2. Вычислить m!+k!-t!




Задание 2. Числа Фибоначчи.
Один  из наиболее часто используемых примеров применения рекурсии - это числа Фибоначчи.  Каждый элемент ряда Фибоначчи является суммой двух предшествующих элементов, т.е.
         1   1   2   3   5   8   13   21   34    55   …
Числа определяются следующим образом:
         x1=x2=1
         xn=xn-1+xn-2 при n > 2

Найти n-ое число Фибоначчи.

           Тесты         Посмотреть решение           

Экспериментальный раздел


1. Написать рекурсивную функцию вычисления xn, где n>0.
Указание: для решения будем использовать равенства xn=1, при n=0, и xn=x·xn-1, при n>0.

2. Вычислить xn-yk+(x-y)n+k.




Задание 3. Ханойские башни. (Задачу и рассказ придумал французский математик Люка в 1883 году.)
В центре мира в землю вбиты 3 алмазных  шпиля. На одном из них 64 золотых диска убывающих  радиусов (самый большой – нижний). Буддийские монахи день и ночь переносят диски с одного шпиля на другой.
Правила: переносить только по одному диску и нельзя больший класть на  меньший.
Когда все диски перенесут, наступит конец света.

Обозначим для определенности шпили (или стержни) как A, B, C. По условию задачи надо перенести N дисков с A на B, используя промежуточный стержень C.
Если N=1, то все просто (перекладываем диск с A на B) и заканчиваем процедуру переноса.
 Иначе (если N>1), переложим сначала N-1 дисков с A на C (используя B в качестве промежуточного стержня), затем перекладываем 1 диск (самый большой) с A на B и, наконец, переносим N-1 диск с C на B (используя стержень A).
Для решения этой задачи  необходимо совершить 2N –1 действий. Если тратить на каждое действие по одной секунде, то (264-1) : (365*24*60*60)= 584 942 417 355,07 лет понадобится легендарным жрецам, чтобы исполнить свою работу.

Предположим, с первого столба А надо перенести на третий С n дисков. Диски пронумерованы в порядке возрастания их диаметров. Предположим, что мы умеем переносить n-1 дисков. В этом случае n дисков перенесем посредством следующих шагов:
1. верхние n-1 дисков перенесем с первого на второй, пользуясь свободным третьим столбом;
2. последний диск наденем на третий столб;
3. n-1 дисков перенесем на третий, пользуясь свободным первым столбом.

Аналогичным образом можно перенести n-1, n-2 и т.д. дисков. Когда n=1, перенос осуществляется непосредственно с первого столба на третий.

               Тесты              Посмотреть решение           


Важно:

1. Всегда предусматривайте выход из рекурсии. Если выхода вы не предусмотрели, ваша программа зависнет.

2. При вызове рекурсивных функций их код перемещается в стек, и локальные переменные размещаются там же, потому хорошо рассчитывайте максимальную глубину "самовызовов" вашей функции. И если вы получили ошибку в процессе выполнения типа "out of memory" - это из-за переполнения стека. Пересмотрите свой алгоритм: наиболее вероятно, что рекурсия заходит слишком глубоко (или бесконечно глубоко, если неправильно реализован из нее выход).

3. Рекурсия - это не способ быстрого решения. Сначала придумайте алгоритм, а потом сделайте его рекурсивную (при надобности) реализацию.





Алгоритм Евклида для нахождения НОД двух чисел: из большего числа вычитаем меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД этих чисел.

Function nod(a,b:integer):integer;
Begin
If (a=0) or (b=0) then begin  nod:=a+b; exit end;
If a>b then nod:= nod(a-b,b) else nod:=nod(a,b-a);
End;


Экспериментальный раздел


1. Найти НОД пяти чисел.

2. Найти НОК пяти чисел.


Задания для самостоятельного решения

1. Дано натуральное число N. Вычислите сумму цифр от 1 до N.
При решении этой задачи нельзя использовать циклы и массивы.

2. Дано натуральное число N. Вычислите сумму его цифр. При решении этой задачи нельзя использовать циклы и массивы. Разрешена только рекурсия и целочисленная арифметика.


Тест