2
$\begingroup$

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_] := ... ?

$\endgroup$
3
  • $\begingroup$ 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]? $\endgroup$
    – Mr.Wizard
    Jun 10, 2014 at 15:58
  • $\begingroup$ Perhaps you want to get rid of the semicolon? $\endgroup$
    – Yves Klett
    Jun 10, 2014 at 16:02
  • $\begingroup$ @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. $\endgroup$
    – RunnyKine
    Jun 10, 2014 at 17:22

1 Answer 1

5
$\begingroup$

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}} *)
$\endgroup$
4
  • $\begingroup$ I thinkl that RSolve should have f[n] == 1 + f[n - 2] + f[n - 1]. $\endgroup$ Jun 10, 2014 at 21:19
  • $\begingroup$ @Daniel Indeed, thanks for the correction! $\endgroup$
    – Szabolcs
    Jun 10, 2014 at 21:23
  • $\begingroup$ @Daniel Do you know why FunctionExpand[Fibonacci[n], n \[Element] Integers] refuses to expand? It prevents Assuming[n \[Element] Integers, Simplify@FunctionExpand[...]] from working. $\endgroup$
    – Szabolcs
    Jun 10, 2014 at 21:29
  • $\begingroup$ I do not know. I expected it to do something myself. $\endgroup$ Jun 10, 2014 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.