Рекурсия в Паскаль, рекурсивные функции и процедуры

На занятии будет рассмотрено понятие рекурсии в Паскаль. Разобраны и решены примеры использования рекурсии

Рекурсия

Если в теле функции встречается вызов самой этой функции, то это и есть рекурсия.

Рекурсивностью в Паскале могут обладать как функции, так и процедуры.

По сути, рекурсия может быть бесконечной. Но, как и любой другой алгоритм, она обязана выдавать результат своей работы за некое определенное количество операций.

Поэтому важно: На каждом шаге выполнения рекурсивного тела процедуры или функции обязательно либо изменение параметра данной функции, либо наличие условия, при котором она больше себя не будет вызывать!

Рассмотрим простой пример использования рекурсивной процедуры:

Пример: Напечатать последовательность чисел в обратном порядке, используя рекурсивный вызов процедуры. Например:
row (5) = 5 4 3 2 1
Из условия задачи ясно, что условием завершения рекурсии будет сам аргумент функции, который следует уменьшать на единицу, пока он >= 1.

procedure row(n:integer);
begin
     if n >=1 then begin
        write (n, ' ');
        row(n-1)
     end;
end;
begin
    row(10);
end.

Теперь рассмотрим более сложный пример использования рекурсии в Паскаль.

Пример: Написать рекурсивную процедуру, выводящую цифры, переданного ей в качестве фактического параметра числа, в обратном порядке.

Например: при переданном функции числе 3078, должно в итоге вернуть 8703
Использовать операции div и mod.

procedure reverse (n: integer);
  begin
       write (n mod 10);
       if (n div 10) <> 0 then
         reverse(n div 10)
  end;
  begin
  writeln;
  reverse(3078);
  end.

Рекурсия: Распечатать последовательность, используя рекурсию:
25,23,21,19,17… 0

А теперь посмотрим, как используется рекурсия при вычислении факториала в Паскаль.

Пример: Создать рекурсивную функцию для вычисления факториала числа

Подсказка:
2!=2*1=2
3!=3*2*1=6
Выводим формулу a!=a*((a-1)!)

var x: integer;
   function fact (a: integer): integer;
   begin
        if (a<=1) then
          a:=1
        else
          a:=a*(fact(a-1));
   fact:=a;
end;
begin
writeln('Число?');
readln(x);
writeln(fact(x));
end.

Рекурсия: Написать рекурсивную функцию sumTo(n), которая для данного n вычисляет сумму чисел от 1 до n, например:
sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
...

Рекурсия: Написать рекурсивную функцию определения степени числа.

Дополните код:

var x,y: integer;
function stepen (a,b: integer):integer;
var ...
begin
  ...
end;
begin
  writeln('число?');
  readln(x);
  writeln('степень?');
  readln(y);
  writeln(stepen(x,y));
end.

Рекурсия: Необходимо сымитировать работу цикла for. Выводить каждый раз слово «привет» и значение счетчика. Для этого использовать переменную счетчика шагов, которую нужно реализовать, как параметр процедуры. Второй параметр – общее количество шагов (количество итераций цикла).

Дополните код:

procedure LoopFor(i, n: integer);
{Первый параметр – счетчик шагов, второй параметр – общее количество шагов}
begin
  ...                     
end;
begin
  LoopFor(1,10);                    
end.

Рекурсия: Найти НОД методом Евклида (алгоритм Евклида). Использовать рекурсивную процедуру.

Для чисел 3430 и 1365:

остаток от деления 3430 на 1365	3430 mod 1365 = 700
остаток не равен нулю, повторим то же действие, подставив вместо первого числа второе, а вместо второго – остаток	1365 mod 700 = 665
остаток также не нуль, поэтому еще одно деление	700 mod 665 = 35
остаток также не нуль, поэтому еще одно деление	665 mod 35 = 0
остаток нуль	НОД равен 35

Рекурсия: Распечатать первые 10 чисел Фибоначчи (до 21), используя рекурсивную процедуру с двумя параметрами.
Результат должен быть: 1 2 3 5 8 13 21 34 55 89
Дополните код:

procedure fib (i,n: integer);
  begin
       writeln (i+n,' ');
       if ... then
           fib(...,...)
  end;
begin
  fib(0,1);
end.

Потренируйтесь в решении задач по теме, щелкнув по пиктограмме:

К оглавлению