В
жизни Вам не раз приходилось сталкиваться с рекурсией. Вспомните хотя бы
стихотворение "У попа была собака" или “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!
Из рисунка видно,
что рекурсия связана с многократными вызовами функции, а это несколько менее
эффективно при выполнении по сравнению с использованием цикла. К тому же
требует больше памяти. Однако рекурсивные версии программ, как правило, гораздо
короче и нагляднее, не требуют наличия цикла и параметра цикла.
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 году.)
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. Вычислите сумму его цифр. При решении этой задачи нельзя
использовать циклы и массивы. Разрешена только рекурсия и целочисленная
арифметика.