понеділок, 15 вересня 2014 р.

Поняття рекурсивних програм

Поняття рекурсивних програм


Підпрограми, які містять виклики самих себе, 
називають рекурсивними, 
а використання таких підпрограм - рекурсією.

Прикладом візуальної рекурсії, відомої як ефект Дроста, може бути

Російська народна казка-пісня "У попа був собака..." теж є прикладом рекурсії:
У попа був собака, він її любив
Вона з'їла шматок м'яса, він її убив
У землю закопав,
Напис написав:
"У попа був собака, він її любив
Вона з'їла шматок м'яса, він її убив
У землю закопав,
Напис написав: ...

Застосування рекурсії дає можливість одержувати витончені алгоритми. Рекурсивне звернення до процедури або функції має сенс тоді, коли сам алгоритм визначений рекурсивно, тобто визначення чергового невідомого значення відбувається через її раніше обчислені значення.

Частина оперативної пам'яті ПК, де зберігається інформація про всі незавершені стани рекурсивних процедур та функцій, називається стековою.

Її максимальний розмір становить (....)  Кбайт.
Коли в стековій пам'яті не залишається інформації про жоден варіант незавершеної функції або процедури, рекурсія вважається завершеною.
Задача №1
Дано ціле невід'ємне число n. Обчислити n! n!=1*2*3*...*n, 0!=1
Розв'язання
Розглянемо приклад: 5!=1*2*3*4*5. Але 1*2*3*4=4!, то 5! = 4!*5. А загалом n!= (n-1)!*n. Це рекурентна формула переходу від обчислення n! до (n-1)!, тобто до факторіалу попереднього числа. Тривіальними випадками (випадками, результат яких нам точно відомий) є n=0, бо 0!=1, і n=1, бо 1!=1.
Отже, ми маємо залежність: 
Алгоритм матиме такий вигляд:
алг ціл Факторіал (ціл k)
арг k
поч
якщо (k=0) або (k=1)
то знач:= 1
інакше знач:= Факторіал(к-1)*k
все
кін		алг Обч_факторіалу (ціл n, ціл rez)
арг n
рез rez
поч
rez:= Факторіал (n)
кін

Нехай n=3. Тоді дана програма працює наступним чином: із основної частини програми здійснюється виклик функції Факторіал для аргументу 3. Формальна змінна к у функції набуває значення 3. Здійснюється перевірка умов 3=0 або 3=1. Оскільки жодна з умов не виконується, то ми переходимо до рекурентної формули Факторіал(2)*3. Тимчасово припиняється виконання обчислень на даному етапі, для значення Факторіал(2) виділяється пам'ять і знову здійснюється виклик функції Факторіал для аргументу 2.
Формальна змінна к набуває значення 2. Оскільки умови 2=0 або 2=1 не виконуються, то переходимо до рекурентної формулиФакторіал(1)*2. Знову тимчасово припиняється виконання поточної функції, а викликається функція Факторіал для значення 1.
Змінна к набуває значення 1. Умова 1=1 виконується, тому поточна функція набуває значення 1 і повертає його. Робота функції Факторіалдля значення 1 припиняється.
Повертаємось до тимчасово припинених обрахунків Факторіал(1)*2= 1*2=2. Тепер робота і цієї функції завершена. Вона повертає значення2.
Повертаємось до обрахунків Факторіал(2)*3 = 2*3=6. Роботу завершено і в основний блок програми повертається значення 6. Змінна rezнабуває значення 6.
Програма
Program Obch_faktorial;
Uses Crt;
Var
n : integer;
rez : longint;
function Faktorial (k : integer) : longint;
begin
if (k=0) or (k=1)
then Faktorial : = 1
else Faktorial : = Faktorial(k-1)*k;
end;
BEGIN
ClrScr;
Write(‘n= ');
Readln(n);
rez : = Faktorial(n);
Write(‘rez= ', rez);
Readkey;
END.
1. Введіть значення виразу (2*3!+5!) div 4!
 
2. Які подання 10! є правильними?
1) 8!*9*10;
2) 8!*10;
3) 9!*10;
4) 1*2*4*5*6*7*8*9*10.
3. Чи вплине на кінцевий результат роботи алгоритму заміна
       якщо (k=0) або (k=1)
                то знач:= 1
                інакше знач:= Факторіал(к-1)*k
        все на
       якщо k=0
                 то знач:= 1
                 інакше знач:= Факторіал(к-1)*k
       все
1) так;
2) ні.
Задача № 2
Дано натуральне число n. Обчислити n-ий елемент послідовності чисел Фібоначі.          1, 1, 2, 3, 5, 8, 13, 21, 44, ...
Історичні відомості
У ХІІІ ст. при розв'язуванні задачі про "розмноження кроликів" відомий італійський математики Фібоначі відкрив рекурентну формулу:F(n)= F(n-1)+F(n-2), яка при початкових умовах F(1) = F(2) = 1 породжує знамениті числа Фібоначі: 1, 1, 2, 3, 5, 8, ... Ці числа в подальшому стали добре відомими, особливо в біології, де вони виражають так званий "закон філлотаксису", яким керуються процеси росту багатьох біологічних структур.
Проте є і нерекурсивна формула обчислення n-ого елемента послідовності Фібоначі. Про неї ви можете прочитати ТУТ:  Числа Фибоначчи. Формула Бине
Отже, n-е число Фібоначі можна обчислити   
Алгоритми

алг ціл Фібоначі (ціл  k)
       арг k
поч
       якщо (k=1) або (k=2)
                 то знач:= 1
                 інакше знач:= Фібоначі(к-1) + Фібоначі(к-2)
       все
кін		алг Числа_Фібоначі (ціл n, ціл rez)
        арг  n
        рез rez
поч
      rez:= Фібоначі (n)
кін


4. Введіть 10-е число Фібоначі.
 
5. Чи вплине на результат роботи алгоритму заміна фрагменту
         якщо (k=1) або (k=2)
                  то знач:= 1
                  інакше знач:= Фібоначі(к-1) + Фібоначі(к-2)
         все  на
       якщо (k=1)
                то знач:= 1
                інакше знач:= Фібоначі(к-1) + Фібоначі(к-2)
       все
1) так;
2) ні.
6. Що буде виконуватись на 5-ому кроці роботи алгоритму, якщо на 1-ому здійснюється виклик функції Фібоначі(10)?
1) Фібоначі (7);
2) Фібоначі (6);
3) Фібоначі (5);
4) Фібоначі (7)+ Фібоначі (6).
7. Введіть послідовність кроків конструювання програми.
      1)     else Fibonachi := Fibonachi (k-1) + Fibonachi (k-2);
         end;
      2) Write(‘rez= ', rez);
      3)    Readkey;
         END.
      4) Var
              n : integer;
              rez : longint;
      5) function Fibonachi (k : integer):longint;
          begin
              if (k=1) or (k=2)
      6) Readln(n);
          rez:= Fibonachi (n);
      7) then Fibonachi:= 1
      8) Program Chisla_Fibonachi;
              Uses Crt;
      9) BEGIN
               ClrScr;
               Write(‘n= ');
 
Опубліковано о

Немає коментарів:

Дописати коментар

Підписатися на: Дописати коментарі (Atom)