Практика программирования (Бейсик, Си, Паскаль)
         

считается рекурсивной, если она пытается


Рекурсивные функции и процедуры

В простейшем варианте процедура (функция) считается рекурсивной, если она пытается вызвать сама себя. Математики нередко прибегают к рекурсивному определению функций:

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.