Рекурсия в Pascal

рекурсия

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

Начнемс... Для начала следует разобраться с простым определением рекурсии: "Рекурсия - это самовоспроизведение". На этом этапе следует просто смериться с тем, что функция будет вызывать саму себя. Обращение будет происходить непосредственно внутри самой функции.

function noname() begin noname(); end; 

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

пример рекурсии: Если у вас жирное пятно на платье,не переживайте. Пятна от масла убираются бензином.Пятно от бензина раствором щёлочи.Щелочь убирается эссенцией.След от эссенции потрите маслом.Hу,а как убрать пятна от масла,вы уже знаете!

Давайте рассмотрим рекурсию на примере факториала, для тех кто забыл !n = 1*2*3*4..*(n-1)*n. Если вы вдруг незнакомы с понятием функция, вам следует восполнить ваш пробел, статья на эту тему уже написана тут.
Для начала мы создадим "шапку", в которой укажем входящий параметр "n" и укажем его тип "LongInt".

function f(n:LongInt):LongInt; 

Суть алгоритма в постепенном уменьшении параметра, иными словами мы идем в обратном направлении, считая факториал с конца ((n-1)*(n-2)..3*2*1). Для лучшего понимания алгоритма я рекомендую ознакомится с блок-схемой программы: 

рекурсия

Примечание: красной стрелкой обозначается самовызов функции.

Следует отметить, что функция видит лишь те переменные, которые ей передали. Т.е. если вы создали переменную A=5, то функция ей не увидит, если использовать прямой вызов (стандартное обращение к переменной). 

Ну а теперь давайте рассмотрим тело программы

if n<1 
    f:=1
else
    f:=n*f(n-1);

А теперь давайте посмотрим на всю функцию целиком:

function f(n:LongInt):LongInt; 
begin
if n<1 
    f:=1
else
    f:=n*f(n-1);
end;

Зачем нужна рекурсия? Главная задача рекурсии в обходе деревьев, обращение к корням которых возможно лишь с помощью рекурсии.

↑ Расскажите друзьям о статье


Comments system Cackle

© EduNow.su — материалы подлежат полному/частичному копированию при указании прямой ссылки на источник. (Сегодня 29.06.17)