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$
  • $\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 '14 at 15:58
  • $\begingroup$ Perhaps you want to get rid of the semicolon? $\endgroup$ – Yves Klett Jun 10 '14 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 '14 at 17:22
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}} *)
| improve this answer | |
$\endgroup$
  • $\begingroup$ I thinkl that RSolve should have f[n] == 1 + f[n - 2] + f[n - 1]. $\endgroup$ – Daniel Lichtblau Jun 10 '14 at 21:19
  • $\begingroup$ @Daniel Indeed, thanks for the correction! $\endgroup$ – Szabolcs Jun 10 '14 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 '14 at 21:29
  • $\begingroup$ I do not know. I expected it to do something myself. $\endgroup$ – Daniel Lichtblau Jun 10 '14 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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