рекурсивный алгоритм для чисел Фибоначи

можно и без рекурсии
используй static и один параметр для сброса статической переменной
int get_next_fibo(bool start)
{
  static int fibo;
  if(start)
    fibo=0;
  /*
   * алгоритм
   */
  return fibo
}

Можно и за константное время вычислить требуемое число Фибоначчи, правда я формулу не помню.

F(n) = (pow((1+sqrt(3))/2,5) - pow((1 - sqrt(5))/2,5))/sqrt(5);

pow(..,n)

Так, ради смеха ...

typedef unsigned int uint;

template <uint n> inline uint fib() { return fib<n-1>() + fib<n-2>(); }

template <> inline uint fib<1> () { return 1; }

template <> inline uint fib<0> () { return 1; }

int main() { std::cout<<fib<4>()<<std::endl; };

изврат на лиспе с lexical closure :_)

(defun fibgen ()
  (let ((fn-1 0) (fn-2 0) (fn 1)) #'(lambda ()
				      (setq fn-2 fn-1)
				      (setq fn-1 fn)
				      (setq fn (+ fn-1 fn-2)))))

f = 1 : 1 : zipWith (+) f (tail f)

fib 1 = 1
fib 2 = 1
fib n = fib(n-1)+fib(n-2)

> используй static и один параметр для сброса статической переменной

Угу, и потом долго матюгайся, когда вызовешь это из двух потоков сразу.

> fib n = fib(n-1)+fib(n-2)

Это очень шустро сожрет стек, т.к. не имеем tail recursion, которую компилятор мог бы соптимизировать.

>>используй static и один параметр для сброса статической переменной
>Угу, и потом долго матюгайся, когда вызовешь это из двух потоков сразу.
ну, я так далеко не загадывал :)

В этом и заключается смысл! Берем задачу которая имеет сложность n и дико извращаясь придумываем для ее вычисления алгоритм сложности n! затем ище раз извращаемся придумываем хвостовую рекурсию в результате решение снова имеет сложность n и это теперь является доказательством крутости некоторого семейства языков.

Это хорошо, наверное, что господин Д. Кнут не знает русского арго, а то бы он вам показал: число Фибоначи и алгоритм вычисления факториала--классический пример, когда не надо использовать рекурсию!

> Можно и за константное время вычислить требуемое число Фибоначчи, правда я формулу не помню.

это не константное время, это обман. Формула требует растущей точности флоатов.

У меня так:

int calcfibc (int n, int a=1, int b=0)
{
    if (n<=1) return a;
    return calcfibc (n-1, a+b, a);
};

Используя вот это тождество для матриц 2x2

(F_{n+1}, F_n; F_n, F_{n-1}) = (1,1; 1,0)^n

и рекурсивный алгоритм для вычисления a^n, получаем
алгоритм, работающий за время O(log n)