# Define function that counts recursive fibonacci

If I write

     count=0;
fib[0]:=(count=count+1; 0);
fib[1]:=(count=count+1; 1);
fib[n_] := (count = count+1; fib[n-2] + fib[n-1]);


Then I can type for example

     fib[5]


and then

     count


and I can see how many times the "fib" was used to compute fib[5].

How can I write this as a function that gives me this number immediatly? So for example f[n_] := ... ?

• I'm a little unsure of your goal; what do you mean by "immediately" -- are you trying to avoid doing the recursion itself, or do you simply mean you want f[n] to return the count for fib[n]? – Mr.Wizard Jun 10 '14 at 15:58
• Perhaps you want to get rid of the semicolon? – Yves Klett Jun 10 '14 at 16:02
• @Mr.Wizard, I think the OP means instead of typing count afterwards to get the number, the function f should spit it out. So basically, the latter of your question. – RunnyKine Jun 10 '14 at 17:22

You can just package it up into a function:

fibcounter[k_Integer?NonNegative] :=
Block[{fib, count = 0},
fib[0] := (count++; 0);
fib[1] := (count++; 1);
fib[n_] := (count++; fib[n - 1] + fib[n - 2]);
fib[k];
count
]


If you're looking for a purely functional style, you can do:

Clear[fibc]
fibc[n_] := fibc[n - 1] + fibc[n - 2] + 1
fibc[0] = fibc[1] = 1


Reasoning: fibc[n] returns the number of calls needed to compute fib[n], whihc is the number of calls needed for fib[n-1] plus the number of calls needed for fib[n-2] plus the original call, i.e. 1.

You can even use RSolve to get a closed form of the result:

RSolve[{f[0] == f[1] == 1, f[n] == f[n - 1] + f[n - 2] + 1}, f[n], n]
(* {{f[n] -> -1 + Fibonacci[n] + LucasL[n]}} *)

Simplify[FunctionExpand[%], n ∈ Integers && n >= 0]
(* {{f[n] -> -1 + (1 - 1/Sqrt[5]) (-(2/(1 + Sqrt[5])))^n + (1 + 1/Sqrt[5]) (1/2 (1 + Sqrt[5]))^n}} *)

• I thinkl that RSolve should have f[n] == 1 + f[n - 2] + f[n - 1]. – Daniel Lichtblau Jun 10 '14 at 21:19
• @Daniel Indeed, thanks for the correction! – Szabolcs Jun 10 '14 at 21:23
• @Daniel Do you know why FunctionExpand[Fibonacci[n], n \[Element] Integers] refuses to expand? It prevents Assuming[n \[Element] Integers, Simplify@FunctionExpand[...]] from working. – Szabolcs Jun 10 '14 at 21:29
• I do not know. I expected it to do something myself. – Daniel Lichtblau Jun 10 '14 at 22:03