Реалізація алгоритму.

Вхідні дані:

Число n. В якості робочого регістра для роботи з цією змінною будемо використовувати регист ecx.

Вихідні дані:

Значення n!. Для зберігання цього значення будемо використовувати регістр eax.

Для перевірки умов використовується команду порівняння cmp.

Для здійснення переходів - команди умовного і безусловног переходів : ja і jmp.

TITLE Вычисление факториала (Fact.asm)

INCLUDE Irvine32.inc

.code

main PROC

push 3

call Factorial

exit

main ENDP

Factorial PROC

; --------------------------------------------------------------------I

push ebp

mov ebp,esp

; -------------------------------------------------------------------II

mov ecx,[ebp+8] ; считывание n из стека

; ------------------------------------------------------------------III

cmp ecx, 0

ja L1 ; переход, если n!=0

mov eax,1 ; если n=0

jmp L2 ; выход из процедуры

; ------------------------------------------------------------------III

L1: dec ecx

push ecx

call Factorial

; ------------------------------------------------------------------IV

mov ebx,[ebp+8] ; Загрузим n

mul ebx ; edx:eax = eax * ebx

; ---------------------------------------------------------------------

L2: mov esp,ebp

pop ebp

ret

Factorial ENDP

END main

Программа на C++

int factorial(int n)

{

if(n == 0) return 1;

else return n * factorial(n-l);

}

int main()

{

int n=3, f;

f=factorial(n);

cout<<f;

}

Структура рекурсивных процедур

Структура рекурсивних процедур може набувати три форми:

1. З виконанням дій після рекурсивного виклику :

Приклад. Вивести на екран усі числа від 1 до n

Вхідні дані:

Число n

Вихідні дані: 1 2 3 4 5

Алгоритм:

При n > 1 рекурсивна фунция заноситиме в стек числа в зворотному порядку. При n=1, функція виведе одиницю і здійснить возвтат в зухвалу функцію, яка у свою чергу, виведе чергове значення n на екран і здійснить вихід з функції.

#include <iostream>

using namespace std;

void PrintN(int);

int main()

{

int n=6;

PrintN(n);

system("pause");

}

void PrintN(int n)

{

if(n > 1)PrintN(n-1);

cout<<n<<' ';

}

Результат : 1 2 3 4 5;

2. З виконанням дій до рекурсивного виклику :

Приклад. Вивести на екран усі числа від 1 до n в зворотньому порядку.

Вхідні дані:

Число n

Вихідні дані: 1 2 3 4 5

#include <iostream>

using namespace std;

void PrintN(int);

int main()

{

int n=5;

PrintN(n);

system("pause");

}

void PrintN(int n)

{

cout<<n<<' ';

if(n > 1)PrintN(n-1);

}

Результат : 5 4 3 2 1;

3) з виконанням дій як до, так і після рекурсивного виклику:

Приклад. Вивести на екран усі числа від 1 до n в зворотньому і прямому порядку .

Вхідні дані:

Число n

Вихідні дані: 5 4 3 2 1 1 2 3 4 5

#include <iostream>

using namespace std;

void PrintN(int);

int main()

{

int n=5;

PrintN(n);

system("pause");

}

void PrintN(int n)

{

cout<<n<<' ';

if(n > 1)PrintN(n-1);

cout<<n<<' ';

}

Результат: 5 4 3 2 1 1 2 3 4 5

Многие задачи безразличны к тому, какая форма рекурсивной процедуры для них используется. Однако есть классы задач, при решении которых программисту требуется сознательно управлять ходом работы рекурсивных процедур и функций. Такими, в частности, являются задачи, использующие списки и древовидные структуры данных. Например, при разработке трансляторов широко применяются так называемые «атрибутированные деревья разбора», работа с которыми требует от программиста умения направлять ход рекурсии: одни действия можно выполнять только на спуске, другие — только на возврате. Поэтому глубокое понимание рекурсивного механизма и умение управлять им по собственному желанию является необходимым качеством квалифицированного программиста.

Приклад. Вивести двійкове представлення натурального числа.

#include <iostream>

using namespace std;

void bin(int);

int main()

{

int n=12;

bin(n);

cout<<"\n\n";

system("pause");

}

void bin(int n)

{

if(n > 0) bin(n/2);

cout<<n%2;

}

Приклад. Визначити, чи є задане натуральне число простим

#include <iostream.h>

int simple(int);

int a;

void main()

{

a=28;

int n=a/2;

if (simple(a/2)) cout<<"Chislo "<<a<<" sostavnoe";

else cout<<"\nChislo "<<a<<" prostoe";

cout<<"\n\n";

}

int simple(int n)

{

cout<<"a="<<a%n<<"\t n="<<n<<endl;

if (n==1) return 0;

if (a%n==0) return 1;

simple (n-1);

}

Приклад. Визначити суму членів арифметичної прогресії.

На кожній ітерації:

a= a+ step

n= n-1

sa_n = sa_n + a

#include <iostream>

using namespace std;

void main()

{

double sum_progres (double, double,int);

double a=2.5, step =3.2;

int n=3;

cout<<"\n\nSum progress="<<sum_progres(a,step,n);

cout<<"\n\n";

system("pause");

}

double sum_progres(double a,double step,int n)

{

if(n==0) return 0;

cout<<a<<" ";

return a+sum_progres(a+step,step, n-1);

}

Результат:

2.5 5.7 8.9

Sum progress=17.1

Приклад. Зведення числа a в цілую ненегативну міру n.

#include <iostream>

using namespace std;

void main()

{

double stepen(double,int);

double a=2.5;

int n=3;

if((n%2)==0)

{

a=a*a;

n=n/2;

}

cout<<a<<"v stepeni "<<n<<" ravno "<<stepen(a,n)<<"\n\n";

}

double stepen(double a, int n)

{

if (n==0) return 1;

else return a*stepen(a, n-1);

}

Приклад. Розробити функцію для розрахунку k -го члена послідовності Фібоначчі (послідовність Фібоначчі утворюють числа 1, 1, 2, 3, 5, 8, 13, ..).

Початкові значення: f1=0 і f2=1. Чергове число Фібоначчі дорівнює сумі двох попередніх: записуватимемо його в змінну f3. Тепер значення f2 вже не потрібне і ми скопіюємо f1 в f2 і x в f1.

#include <iostream>

using namespace std;

void Fib1(int n);

void main()

{

int n=10;

cout<<endl<<endl<<Fib1(n)<<endl<<endl;

system("pause");

}

int Fib1(int n)

{

int i, f1 = 0, f2 = 1, f3;

for (i = 2; i <= n; i ++)

{

f3 = f1 + f2;

f1 = f2; f2 = f3;

}

cout<<"n="<<n<<" res="<<res<<"\t\ttime="<<difftime(end,begin)<<endl;

return f3;

}

Рекурсивна функция выглядит намного понятнее, но для больших n (>20) работает в сотни тысяч раз медленнее. Вывод - там, где можно легко обойтись без рекурсии, надо без нее обходиться.

#include <stdio.h>

#include <time.h>

#include <iostream>

using namespace std;

long F(unsigned int n)

{

return n <= 1 ? n : F(n-1) + F(n-2);

}

int main()

{

time_t begin, end;

long res;

for(int n = 20; n < 40; n++)

{

time(&begin);

res = F(n);

time(&end);

cout<<"n="<<n<<" res="<<res<<"\t\ttime="<<difftime(end,begin)<<endl;

}

system("pause");

return 0;

}

Такая запись полностью соответствует закону построения последовательности Фибоначчи — очередной ее элемент равен сумме двух предыдущих. При этом не требуется применять оператор цикла и ду­мать над последовательностью расчета значений пред и предпред.

Результат:

n=20 res=6765 time=0

n=21 res=10946 time=0

n=22 res=17711 time=0

n=23 res=28657 time=0

n=24 res=46368 time=0

n=25 res=75025 time=0

n=26 res=121393 time=0

n=27 res=196418 time=0

n=28 res=317811 time=1

n=29 res=514229 time=0

n=30 res=832040 time=0

n=31 res=1346269 time=0

n=32 res=2178309 time=1

n=33 res=3524578 time=1

n=34 res=5702887 time=1

n=35 res=9227465 time=3

n=36 res=14930352 time=4

n=37 res=24157817 time=6

n=38 res=39088169 time=10

n=39 res=63245986 time=17

Press any key to continue . . .

Заметим, что каждый рекурсивный вызов при n>1 порождает еще 2 вызова функции, многие выражения (числа Фибоначчи для малых n) вычисляются много раз. Поэтому практического значения этот алгоритм не имеет, особенно для больших n.

Одна из главных практически важных областей, где применение рекурсии жизненно необходимо и значительно упрощает решение – задачи на перебор вариантов.