Рассмотрим ещё один пример использования рекурсии – вычисление N-ого по счёту числа Фибоначчи. Числа Фибоначчи составляют последовательность, очередной элемент которой вычисляется по двум предыдущим значениям:

F­n=Fn-1 + Fn-2 .

Нулевое и первое значения должны быть заданы, их значения равны единице. Последовательности такого рода применяются, например, в программах генераторах случайных чисел. Вычисление 20-ого числа Фибоначчи реализовано в программе Fibonacci (Листинг 4). Впрочем, номер числа можно изменить, задав в описании константы другое значение.

Листинг 4. Программа вычисления 20-ого числа Фибоначчи.

program Fibonacci;

uses Crt;

const n=20;

function F(n: word): longint;

begin

if keypressed then

halt;

if (n=0) or (n=1) then

F:=1

else F:=F(n-1)+F(n-2); {рекурсивный вызов}

end;

function G(n: word): longint;

var x,y,t: longint; k: word;

begin

x:=1;

y:=1;

for k:=2 to n do

begin

t:=y;

y:=x+y;

x:=t;

end;

G:=y;

end;

begin

clrscr;

textcolor(lightgray +128);

write(‘Считаю .’);

textcolor(lightgray);

writeln(‘—Ждите ответа--’);

writeln;

writeln(‘Рекурсивный алгоритм : F(‘, n, ’)= ’, F(n));

writeln;

writeln(‘Итерационный алгоритм : F(‘, n, ’)= ’, G(n));

gotoxy(1,1);

clreol;

gotoxy(1,7);

write(‘Нажмите <Enter>’);

end.

В этой программе реализованы два метода решения задачи вычисления числа Фибоначчи. Один назовём итерационным методом – он заключается в прямом программировании итерационной формулы для чисел Фибоначчи. В функции G для этого используются три вспомогательные переменные типа LongInt.

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

2. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ ЭВМ И ИХ ОБРАБОТКА

Личные данные займут в памяти ЭВМ 28 байтов.

Сложение числа и месяца рождения в двоичном формате: +1111

0100

10011

(10011)2=(19)10

Вычитание месяца из числа рождения в двоичном формате: _1111

0100

1011

(1011)2=(11)10

3. РАЗРАБОТКА ПРОГРАММ

3.1. Программа роста банковского вклада по месяцам

Программа спрашивает с защитой от неверного введения данных следующую информацию:

§ начальный размер вклада (1000 .10000);

§ размер периодических платежей (от 1% до 10% от начального вклада);

§ размер процентной ставки вклада (0.5% .4% в месяц).