Вопрос про рекурсию(Фибоначчи) на С?

Question

[gleendo]

int fib(int n) {
  if (n < 2) {
    return 1;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
}


void main() {
  fib(5); // -> выведет 5 число Фибоначчи
}

А как вывести саму последовательность от 0 до n, а не n-ое число

Answer 1

[Владлен Грачев]

Если сделать вывод прямо в функции, то числа будут в обратной последовательности. Первый приходящий в голову вариант — заводить массив (размерность известна) и заполнять его в процессе выполнения функции. И далее выводить уже содержимое этого массива.

Comments

[gleendo]

Пришла идея, но почему то ошибка.
void main() {
clrscr();
int i, n;
for (i = 1; i < n; i++) {
fib(n);
}
getch();
}

но почему то на строке int i, n; выводит ошибку "declaration is not allowed here"

Как это исправить?

[Владлен Грачев]

con_, перенести объявление в начало блока или компилировать по более новому стандарту. Кажется, с ключом типа -std=c99.

Answer 2

[Владислав]

Можно динамическое программирование применить. Плюс к скорости, минус по памяти.
habrahabr.ru/post/113108

Comments

[gleendo]

Спасибо за ответ, но я что не нашел там как реализовать вывод самой последовательности...там только более рациональный метод нахождения n-ого числа.

[Владислав]

Обрати внимание на второй кусок кода, где заполняется массив. Можно его последовательно вывести: это и будет последовательность Фибоначчи