Рекурсия Начальные сведения о рекурсии

Определение рекурсии Рекурсия (от латинского recursio - возвращение) - это такой способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе. Внимание! Для того, чтобы такое обращение не было бесконечным, в тексте подпрограммы должно быть условие, по достижению которого дальнейшего обращения не происходит. Таким образом, рекурсивное обращение может включаться только в одну из ветвей подпрограммы.

Пример рекурсии Хорошей иллюстрацией механизма рекурсии является функция для вычисления факториала натурального числа. Вспомним, что факториалом числа называется произведение всех натуральных чисел от 1 до этого числа включительно: N! = 1*2*3*... *(N-2)*(N-1)*N 1! = 1 0! = 1

Решение без рекурсии Function NonRecFact(N:integer) : LongInt; Var i : integer; {переменная цикла } Res : LongInt; {результат} Begin Res := 1; for i := 1 to N do res := Res*i; NonResFact := Res; End;

Решение с рекурсией Function RecFact(N:integer) : LongInt; Begin if N <= 1 then ResFact := 1 else ResFact := N*ResFact(N-1); End; Задание Используя данную функцию, составьте программу вычисления факториала числа N. Протрассируйте полученную программу в отладчике.

Решение задач Напишите рекурсивный алгоритм нахождения степени числа. а^х=а^(х-1)*а, а^0=1