Совсем недавно начал изучать Си++. После изучения некоторых управляющих структур решил написать программу вычисляющую сотый член последовательности Фибоначи. Написал, работает. Вычисляет очень быстро, сразу после нажатия на клавишу ВВОД. Сегодня дошел до темы Рекурсия и решил на ее основе написать еще одну прогу. Она также должна вычислять соты член последовательности. Написал, скомпилировал без ошибок. Но после запуска она виснет! Процессор на сто процентов, и в месте где должен высветиться результат просто мигает курсор. Не понимаю! Подскажите плиз, в чем моя ошибка или так и должно быть???
Обычная прога:
Код:
//Последовательность Фибоначи
#include <iostream>
using namespace std;
main() {
int counter, a, b, c;
counter = 1;
a = b = 1;
while (counter <= 100) {
c = a + b;
a = b;
b = c;
counter++;
}
cout << c << endl;
return 0;
}
Прога с использованием рекурсии:
Код:
//Вычисление члена последовательности Фибоначи с помощью рекурсии
#include <iostream>
using namespace std;
unsigned long fibonachi(unsigned long);
main() {
unsigned long number = 100, result;
result = fibonachi(number);
cout << result << endl;
return 0;
}
unsigned long fibonachi(unsigned long n) {
if (n == 0 || n == 1)
return n;
else
return fibonachi(n-1) + fibonachi(n - 2);
}
В такой реализации -- да.
Потому что _каждый_ раз при вычислении члена последовательности _заново_ вычисляются все предыдущие.
То есть количество операций сводится где-то к факториалу... Что для 100 при самой грубой оценке -- больше 10^90.
Число вызовов растет экспотенциально.
При рекурсии используется скрытый стек. Количество памяти выделяется около 64 кб, в зависимости от компилятора.
Итак, урок таков: следует избегать рекурсии там, где есть очевидное итерационное решение.
P.S
Читай Никлаус Вирт "Алгоритмы и структуры данных",
Дональд Кнут "Искусство программирования"
У вас нет необходимых прав для просмотра вложений в этом сообщении.
По теме хочу согласиться Crazy, рекурсия вещь опасная и ошибки в алгоритме действий очень трудно отследить, особенно кодгда одна, вде или более рекурсивных активно взаимодействующих функций... Помню всего один случай у себя где ее нельзя было никак обойти (решал тогда задачу изображения фракталов )... ну а вообще частота столкновений с рекурсией это дело сугубо индивидуальное.
Вообще это банальная ошибка переполнения стека. Нужно всегда заботится о завершения рекурсии.
Не всегда есть простое итерационное решение, например задача о восьми ферзях, стабильных браков, оптимального выбора.
)... ну а вообще частота столкновений с рекурсией это дело сугубо индивидуальное.
это тоже своего рода искусство.