Руководство полного чайника по программированию на языке Си


СТЕК И ФУНКЦИИ - часть 4


Многие функции более естественно выражаются через рекурсию. Хотя, часто это приводит к излишним вычислениям по сравнению с итерациями (то есть циклами). Вот пример - числа Фибоначчи.

int fibonacci(int n){ if(n==1 || n==2) return 1;

/* else */

return fibonacci(n-1) + fibonacci(n-2); } void main(){ printf("20ое число Фибоначчи равно %d\n", fibonacci(20)); }

Поскольку тут отсутствует массив для запоминания промежуточных результатов, то этот массив на самом деле неявно моделируется в виде локальных переменных внутри стека вызовов функций. Однако этот способ плох - в нем слишком много повторяющихся действий. Добавим оператор печати - и посчитаем, сколько раз была вызвана fibonacci(1) ?

int called = 0;

int fibonacci(int n){ if(n==1){ called++; return 1;

} else if(n==2) return 1;

return fibonacci(n-1) + fibonacci(n-2); } void main(){ printf("20ое число Фибоначчи равно %d\n", fibonacci(20)); printf("fibonacci(1) была вызвана %d раз\n", called); }

Она была вызвана... 2584 раза!




- Начало -  - Назад -  - Вперед -