Связь с администрацией сайта:       

demo

Среди толпы я одинок

Pascal Вычисление факториала «n» на примере рекурсивной функции

Для начала разберемся, что же такое рекурсивная функция. А рекурсивная функция – это не что иное, как функция, которая вызывает сама себя до тех пор, пока не выполнится условие. Грубо говоря, можно провести аналогию с циклом RepeatUntil. Смысл тот же, но с отличием того, что занимает меньше времени на написание программного кода. В общем-то рекурсивная функция тот же цикл, только не явный, но в использовании намного удобнее. На эти два примера мы сейчас и будем опираться, а разницу вы увидите сами.
 
 
Создадим функцию factorial, в которую будут возвращаться значения с типом Longint, так как полученные значения могут быть огромными.
Примечание: Сначала я напишу полностью код, с мелкими пояснениями, а ниже разберем подробнее, так как я считаю, что для понимания это намного проще, нежели давать программный код кусками и надеяться, что пользователь ничего не упустит.
И если вам покажется объяснения очень трудным для понимания, то прокрутите в конец данной статьи. Там на простых примерах объясняется принцип работы рекурсивной функции.
var n:integer; //Переменная n, для первоначальных данных. 
//До какого числа(включительно) вычислять факториал
function factorial(x:integer):longint; // Наша рекурсивная функция факториала begin if x = 1 then factorial:= 1 else factorial:= x * factorial (x-1); //Условие для выхода
//из тела функции
end; begin writeln('Введите n (n= 1..100)'); // Просим пользователя ввести натуральное число readln(n); //Вводим число writeln('N!=', factorial(n)); //Выводим значение факториала введенного числа путем
//вызова функции factorial(n)
end.

Замечу, если вы плохо разбираетесь в глобальных и локальных переменных, что наше введенное n, в функции будет x. n– глобальная переменная, x– локальная. Значения переменной «x» не уйдут дальше функции, мы сможем ей пользоваться только в теле функции и нигде больше.

Стандартные операторы, такие как readln, writelnя думаю понятны. Поэтому сразу перейдем разбирать написанную функцию factorial.
С виду обычная функция, кроме одного момента, а именно условие if. Здесь именно это условие помогает нам определить условие выхода из функции или продолжение на выполнение.
if x = 1 then factorial:= 1else factorial:= x * factorial (x-1);
Разберем условие с конца, если x>1, получаем factorial:= x * factorial (x-1).  Как же работает это выражение? Вы спросите как так, мы вводим, к примеру, число 5, а он поочередно умножает нам каждое число от 1 до 5?
В дальнейшем для примера буду использовать число 5.
На самом деле очень просто. Сейчас наглядно приведу примеры на простом языке. Можете заметить, что  в каждом случае выражение вызывает функцию факториала(то есть саму себя) и уменьшает значение «x» на единицу, тем самым вычисляем факториал не с 1,  а с 5 и мы получаем, что разбираясь по действиям, происходит следующее:

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

Таблица 1

Вызов функции

Вычисления

Примечание

factorial:= 5 * factorial (5-1)

0 = 5*factorial(4)

Пока что мы не можем вычислить factorial числа 5, так как мы вызвали функцию еще раз и необходимо вычислить теперь факториал 4

factorial:= 4 * factorial (4-1)

0 = 4*factorial(3)

Пока что мы не можем вычислить factorial числа 4, так как мы вызвали функцию еще раз и необходимо вычислить теперь факториал 3

factorial:= 3 * factorial (3-1)

0 = 3*factorial(2)

Пока что мы не можем вычислить factorial числа 3, так как мы вызвали функцию еще раз и необходимо вычислить теперь факториал 2

factorial:= 2 * factorial (2-1)

0 = 2*factorial(1)

Пока что мы не можем вычислить factorial числа 2, так как мы вызвали функцию еще раз и необходимо вычислить теперь факториал 1

x = 1;

if x = 1 then factorial:= 1.

Теперь x = 1 и функция прекращает своё действие и возвращаем 1.

Теперь программа можем вычислить факториалы поочередно от 1 до 5, так как мы больше не вызываем нашу функцию.

  
Как только мы дошли до условия выхода из функции x = 1, получилось следующее:
Таблица 2

Вызов функции

Вычисления

Примечание

factorial:= 2 * factorial (1)

2 = 2*1

В factorial (1) нам вернулось число 1 и записываем значение в factorial = 2;

factorial:= 3 * factorial (2)

6 = 3*2

В factorial (2) нам вернулось число 2 и записываем значение в factorial = 6;

factorial:= 4 * factorial (3)

24 = 4*6

В factorial (3) нам вернулось число 6 и записываем значение в factorial = 24;

factorial:= 5 * factorial (4)

120 = 5*24

В factorial (4) нам вернулось число 24 и записываем значение в factorial = 120;

 
В итоге получаем, что факториал 5 равен 120.
Я с Вами согласен, что немного трудно для понимания и написано очень много. Но это всё примеры работы этой функции и ничего более.
Если мы преобразуем нашу функцию и выведем значение x, то получим следующий результат:
function factorial(x:integer):longint;
begin
  write(' X_Before = ',x); // Число x довычисления factorial (x-1)
   if x = 1 then factorial:= 1 else factorial:= x * factorial (x-1);
   write(' X_After  =  ',x); // Число x послевычисления factorial (x-1)
end;
На экране выведет:
X_Before = 5 X_Before = 4 X_Before = 3 X_Before = 2 X_Before = 1
X_After = 1 X_After = 2 X_After = 3 X_After = 4 X_After = 5
Можете заметить, что до условия он выполняет действия, указанные в таблице 1. А по окончании, когда «x» стал равен 1, он начал выполнять дальнейшие действия, как указано в таблице 2.
А теперь, как и обещал, программный код факториала с помощью Repeat Until для сравнения:
var n:integer;
    summa:Longint;
 begin
     writeln('Введите n (n=1..13)');
     readln(n);
     summa:=1;
       Repeat
         summa:=summa*n;
         n:=n-1;
       Until n = 1; 
     writeln('N!=',summa);
end.
Я думаю, разница сразу бросается в глаза. Хотя принцип очень схож. Там мы вызываем функцию factorial до тех пор, пока xне станет равен 1, и здесь пока nне станет равен 1. Но на деле, понимание работы и использование рекурсивных функций намного упрощает написание кода и занимает меньше времени.
Приведу простенькие примеры из жизни для более глубокого понимания принципа рекурсии(Ведь рекурсия может быть и многосложной, к примеру для поиска выхода из лабиринта или в итоге - зацикленной):
Принцип матрешки . Вам поставили задачу посчитать количество матрешек в каждой из вложенных внутри. Вы же не можете сказать точное количество вложенных матрешек, пока не откроете каждую. Придется открыть каждую матрешку, а потом, уже, вкладывая их в друг друга считать, сколько в каждой из них находится матрешка поменьше. Из этого следует, что в 5-ой матрешке будет 4(но мы не узнаем, пока не откроем все матрешки до 4-ой), в 3-ей матрешке будет 2(но мы не узнаем, пока не откроем все матрешки до 3-ой) и так далее.
Грязное пятно . Бывает порой, что одежда пачкается маслом. Так вот, пятно от масла легко убирается бензином. Теперь проблема, надо оттереть сам бензин, а от бензина поможет раствор щёлочи. Но вот незадача, щелочь. Щелочь уберем эссенцией. Ага, теперь след от эссенции необходимо протереть маслом. А теперь вообще не проблема, как убрать пятно от масла мы уже знаем.
У попа была собака. Все докучные песни-сказки основаны на рекурсии. Только нет условия для выхода из неё. У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: "У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал:…..
Купи слона. Все мы знаем эту шуточную для кого-то игру:
— Купи слона!
— Зачем мне слон?
— Все спрашивают «зачем мне слон», а ты купи слона.
— Отстань!
— Все говорят «отстань», а ты купи слона…
Яркий пример использование рекурсии. То есть берутся прошлые входные данные «зачем мне слон», «отстань»  и выполняется та же функция «купи слона» с новыми параметрами. Рекурсивная процедура будет выглядеть вот так:
procedure buy_elephant(S_local_answer:String);
begin
  var answer:String;
  writeln('Все говорят "'+S_local_answer+'", а ты купи слона');
  writeln('Введите ответ');
  readln(answer);
 buy_elephant(answer);
end;
 begin
     buy_elephant('Чего тебе?');
end.
          В этом всём и заключается основной принцип функций-процедур-рекурсий. Не забываем, что решает всё практика и только практика. Без неё никакого понимания не придет. Можете, как и я, найти такие шуточные игры или песни-сказки и на их примере потренироваться в использовании рекурсивной функции или процедуры. В дальнейшем пригодится для решения очень многих задач, вставших перед вами.
 
 
Голосуй
(0 Голоса)
Оставьте комментарий

Поля, отмеченные звездочкой(*) обязательны для заполнения. HTML теги не приветствуются.

Вход на сайт