Рекурсивная функция

Если функция вызывает саму себя, то возникает рекурсия.

Рекурсия – мощный инструмент разработки программ, когда большие объемы действий могут быть записаны кратко.

Рекурсию можно рассматривать как еще одну управляющую структуру – управление из точки рекурсивного вызова передается на начало функции.

Ключевым фактором обеспечения рекурсии является использование стека. Стек – особое устройство оперативной памяти по принципу: последним пришел – первым вышел.

При выполнении программы в стек сохраняются параметры функции, внутренние локальные переменные и адреса возврата при завершении функции.

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

Поэтому при написании рекурсивной функции мы должны стремиться к минимизации количества параметров, количества локальных переменных, количества рекурсивных вызовов или к их оптимальному соотношению.

Числа Фибоначчи

, n>2

a=0, b=1, c=a+b, a=b, b=c

int Fib(int n)

{

if(n==0)

return 0;

else if(n==1)

return 1;

else

return Fib(n-2)+Fib(n-1);

}

int main(void)

{

cout<<Fib(5)<<endl;

return 0;

}

Задача: вычислить факториал числа N

N!=N*(N-1)

int fakt(int n)

{

if ((n==1)or(n==0))

return n;

else

return fakt(n-1)*n;

}

+

40. Передача функции в другую функцию через указатель.