|
.:
Учебник по практическому программированию ( Бейсик, Си, Паскаль ) :.
  
Глава
5.
Рекурсивные
функции и процедуры
В простейшем
варианте процедура (функция) считается рекурсивной, если она пытается вызвать
сама себя. Математики нередко прибегают к рекурсивному определению функций:
n! = n*(n-1)!
Естественно,
что при таком хождении "по кругу" должно быть предусмотрено условие
выхода, иначе вычислительный процесс может продолжаться бесконечно долго. В
примере с факториалом тело процедуры на Паскале может выглядеть следующим образом:
if n < 2
then fact:=l else fact:=n*fact(n-1);
В более сложных
вариантах рекурсивная процедура входит в состав двух или более процедур, последняя
из которых вновь обращается к начальной:
А -> В ->
А -> В -> А ...
В язык Паскаль,
требующий описать любой объект до его использования, пришлось включить специальное
опережающее объявление рекурсивных процедур, сопровождаемое служебным словом
forward:
{ Опережающее
объявление первой в цепочке процедуры А }
procedure А(<список
параметров>);
forward; { Описание
последней в цепочке рекурсивной процедуры В }
procedure В(<список
параметров>);
begin
А(...); { Вызов
рекурсивной процедуры А }
end; { Описание
первой в цепочке рекурсивной процедуры А }
procedure A;
{ Здесь можно не повторять список аргументов } begin
В (...); { Вызов
рекурсивной процедуры В } end;
Несмотря
на все изящество рекурсивных программ, их работа сопряжена с повышенными затратами
машинного времени и ресурсов по памяти. При каждом новом вызове рекурсивной
процедуры приходится сохранять значения всех ее локальных переменных и выделять
новые участки памяти для очередной порции локальных данных. Как правило, рекуррентный
алгоритм с большими или меньшими усилиями можно превратить в обычный циклический
процесс. Например, фрагмент программы, вычисляющей n!, может выглядеть следующим
образом:
Р = =1;
for i:=l to
n do p:=p*i;
fact:=p;
Однако, как
бы ни относились разные программисты к рекурсии, следует признать, что некоторые
рекурсивные программы выглядят очень эффектно и их алгоритмы оказываются намного
более прозрачными (см., например, процедуру быстрой сортировки quicksort илиигровую
программу "Ханойские башни").
Задачи,советы
и ответы
Задание
5.01. Числа Фибоначчи
История чисел
Фибоначчи восходит к началу XIII в., когда итальянский математик Леонардо Пизанский
нашел изящное решение задачи о размножении кроликов. Пусть в начале эксперимента
имеется единственная пара -самец и самка, которые приносят каждый месяц приплод,
состоящий также из самца и самки. Дети включаются в цикл продолжения рода через
два месяца. Требуется определить количество пар, спустя k месяцев после начала
эксперимента. Ситуация не так уж и сложна:
- в начале эксперимента
— 1 родительская пара;
- через 1 месяц — 2
пары (родители и дети первого поколения);
- через 2 месяца — 3
пары (родители и дети двух поколений);
- через 3 месяца — 5
пар (родители, дети трех поколений, внуки от первого поколения);
- через 4 месяца — 8
пар (родители, дети четырех поколений, 2 пары внуков от первого поколения,
1 пара внуков от второго поколения);
- ..............................................................................
Леонардо
догадался, что числа указанной последовательности связаны рекуррентным соотношением:
fk
= fk-2 + fk-1
В разных
учебниках последовательность чисел Фибоначчи дополняют либо еще одной единицей,
либо нулем и единицей:
1,1,2,3,5,8,13,21,34,55,...
0,1,1,2,3,5,8,13,21,34,.....
Последний
вариант принят в приводимых ниже программах, отсчет порядковых номеров чисел
Фибоначчи ведется от 0. Диапазон действия этих программ не так уж велик: fit>(22)=17711,
fib(23) =28657 и уже 24-е число выходит за пределы предусмотренного диапазона.
Если вас заинтересуют числа с большими номерами, то можно изменить тип функции
fib или воспользоваться формулой Бинэ:
f ib (k) = (
( (1+sqrt (5) ) /2)*k- ( (1-sqrt (5) ) /2} ^k) /sqrt (5)
Наиболее
известное применение чисел Фибоначчи — оптимальный выбор точек при поиске экстремума
унимодальной функции на заданном отрезке. Рекурсивная реализация нахождения
чисел Фибоначчи абсолютно неэффективна, т. к. в теле процедуры при каждой итерации
происходит два обращения к этой же процедуре и объем вычислений с ростом k возрастает
почти в геометрической профессии.
Программа
5_01.bas
DECLARE FUNCTION
FIB%(N%)
INPUT "Задайте
порядковый номер числа Фибоначчи - ",N%
PRINT "Число
Фибоначчи с номером ";N%;" равно ";FIB%(N%)
END
FUNCTION FIB%(N%)
IF N% < 2
THEN
FIB%=N% ELSE
FIB%=FIB%(N%-2)+FIB%(N%-1)
END IF
END FUNCTION
Программа
5_01.с
#include <stdio.h>
#include <conio.h>
Совет
1 (общий)
Алгоритм
нахождения наибольшего общего делителя (нод) двух натуральных чисел приписывают
Евклиду. Он базируется на трех сравнительно тривиальных утверждениях:
HОД(kl,k2)
= HOД(k2,kl) // поэтому можно считать, что kl < k2
HОД(0,k)
= k // неудивительно, т.к. О делится на все
HОД(kl,k2)
= HОД(k3,kl) // k3 - остаток от деления k2 на kl. В истинности последнего несложно
убедиться, если записать: k1*m + k3 = k2 // m - частное от деления k2 на k1
Если kl
и k2 делятся на свой нод, то и k3 делится на это же число без остатка. Поэтому
алгоритм Евклида состоит из следующих шагов:
- Если первое число
kl больше второго, то поменять их местами.
- Если kl=0, то вычисления
прекращаются.
- Находим остаток
от деления k2 на kl и заменяем им большее число.
- Повторяем шаги,
начиная с первого.
Совет
2 (общий)
За
счет небольшой потери эффективности от перестановки большего и меньшего чисел
можно отказаться. При этом подпрограмма лишний раз обратится к себе:
НОД(120,84)=НОД(84,120)=НОД(36,84)=НОД(12,36)=НОД(0,12)==12
Поэтому тело функции можно построить из единственного условного оператора.
Программа
5_02.bas
DECLARE FUNCTION
NOD&(NlS,N2&)
PRINT "Введите
2 натуральных числа, разделяя их запятой"
INPUT "",M&,N&
PRINT "Их
наибольший общий делитель равен ";NOD&(M&,N&)
END
FUNCTION NOD&(N1&,N2&)
IF Nl&=0 THEN
NODS=N2&
ELSE
NOD&=NOD&(N2&
MOD N1&,N1&)
END IF
END FUNCTION
Программа
5_02.с
#include <stdio.h>
#include <conio.h>
long nod(long
nl,long n2);
main() {
long m,n;
printf("\n
Введите 2 натуральных числа, разделяя их пробелом\n");
scanf("%ld
%ld",&n,&m);
printf("Их
наибольший общий делитель равен %ld",nod(m,n));
getch(); }
long nod(long
n1,long n2) {
if(nl==0) return
n2;
return nod(n2%nl,nl);
}
Программа
5_02.pas
program Euclid;
var
n,m:longint;
function nod(nl,n2:longint):longint;
begin
if nl=0 then
nod:=n2
else nod:=nod(n2
mod n1,n1);
end;
begin
writeln('Введите
два натуральных числа');
readln(n,m);
writeln{'Иx
наибольший общий делитель равен ',nod(n,m));
readln; end.
Задание
5.03. Ханойские башни
Игра "Ханойские
башни" была придумана французским математиком Э. Люка в конце XIX в. На
подставке установлены три шпильки, которые
мы условно
назовем А, в и с. На шпильку А надето k дисков разного диаметра таким образом,
что они образуют "правильную" пирамиду (каждый диск, расположенный
выше, имеет диаметр меньший, чем у всех, лежащих ниже). Цель игры заключается
в переносе пирамиды на шпильку с. При этом за один ход разрешается переложить
один диск, надевая его на одну из шпилек таким образом, чтобы верхний диск всегда
был меньшего диаметра.
Можно показать,
что число ходов, необходимое для решения этой задачи, равно 2k-i.
Для k=1 и k=2 это легко проверяется. Дальнейшие рассуждения выполняются по индукции:
если это справедливо для любого k-1, то докажем справедливость утверждения о
числе шагов и для любого k. Предположим, что мы умеем переносить пирамиду из
k-1 дисков за 2k-1-1 ходов. Тогда для переноса башни из k дисков
можно поступить следующим образом:
- переносим верхние
k-l диски со шпильки А на шпильку в;
- переносим оставшийся
самый большой диск со шпильки А на шпильку с (это еще один ход);
- используя освободившуюся
шпильку А в качестве рабочей, переносим пирамиду из k-1 диска со шпильки в
на шпильку с.
Таким образом,
число ходов, которое мы затратили для переноса пирамиды из k дисков, равно:
2k-1
- 1 + 1 + 2k-1 -1 = 2k-l
Совет
1 (общий)
Для
построения рекурсивной программы необходимо последовательно уменьшать размерность
задачи, сводя ее на каждой итерации к последовательности трех описанных выше
перемещений. Для этой цели нам понадобятся две процедуры:
MoveAll(k,from,to,tmp)
MoveOne(from,to)
Первая
из них выполняет шаги по переносу пирамиды из k дисков со шпильки from на шпильку
to, используя в качестве рабочей шпильку tmp. Вторая переносит один диск со
шпильки from на шпильку to.
Совет
2 (QBasic)
Переменная
т% введена для нумерации ходов. Для того чтобы ее значение сохранялось после
очередного перемещения одного диска в заголовке подпрограммы MoveOne использован
указатель STATIC.
Совет
3 (Паскаль)
В
программе нельзя использовать идентификатор to, т. к. он занят под служебное
слово в операторе цикла for.
Программа
5_03.bas
DECLARE SUB
MoveAll(k%,from$,to$,tmp$)
DECLARE SUB
MoveOne(from$,to$)
CLS
INPUT "Введите
количество дисков ",k%
MoveAll k%,"A","C","B"
END
SUB MoveAll
(k%, from$, to$,tmp$)
IF k%=0 THEN
EXIT SUB
MoveAll k%-l,from$,tmp$,to$
MoveOne from$,to$
MoveAll k%-l,trap$,to$,from$
END SUB
SUB MoveOne(from$,to$)
STATIC
m%=m%+l
PRINT USING
"#### : &--> & ";m%;from$;to$ END SUB
Программа
5_03.с
#include <stdio.h>
#include <conio.h>
void MoveAll(int
k,char from,char to,char trap);
void MoveOne(char
from,char to);
int m=0;
main () {
int k;
clrscr () ;
printf("\n
Введите количество дисков - ");
scanf("Id",&k);
MoveAll(k,'A','C','B');
getch(); }
void MoveAll(int
k,char from,char to,char tmp)
{
if(k==0) return;
MoveAll(k-1,from,tmp,to);
MoveOne(from,to);
MoveAll(k-1,tmp,to,from); }
void MoveOne(char
from,char to) {
m++;
printf("\n%4d
: %c --> %c",m,from,to); }
Программа
5_03.pas
program Hanoi;
uses Crt; var
k:integer; const
m: integer=0;
procedure MoveOne(from,tol:char);
begin
inc (m) ;
writeln(m:4,from:2,
' —> ',tol);
end;
procedure MoveAll(k:integer;from,tol,tmp:char);
begin
if k = 0 then
exit;
MoveAll(k-1,from,tmp,tol);
MoveOne(from,tol);
MoveAll(k-1,tmp,tol,from);
end;
begin
clrscr;
write('Введите
количество дисков - ') ;
readln(k);
MoveAll(k, 'А',
'С', 'В');
readln;
end.
| 
