Fibonacci Sequence Generator

Question

I'm trying to write a function in Workbench which will generate a Fibonacci sequence starting with F0 = 0 and F1 = 1. So far I have this written

fibonacciSequence[n_] := 
Module[{fPrev = 0, fNext = 1, i = 0}, 
While[i++ < n, {fPrev, fNext} = {fNext, fPrev + fNext}];
fNext]

How do I modify the function to make it print out a list like the one below when fibonacciSequence[15] is called?

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610}

Sorry, but I am very new to Mathematica and my professor didn't give us much instructions or examples of similar functions.

Answer 1

I'm really surprised if this question isn't a duplicate, but since I failed to find one that asked about the Fibonacci sequence rather than someone using it as an example, I'll answer.

The most natural approach, besides using the built-in Fibonacci function, recursion:

f[0] = 0; f[1] = 1;
f[n_] := f[n] = f[n - 1] + f[n - 2]  (* note memoization *)

Array[f, 10]

{1, 1, 2, 3, 5, 8, 13, 21, 34, 55}

Better performing may be Nest and NestList:

fibonacciList[n_] := Module[{x = 0}, NestList[x + (x = #) &, 1, n - 1]]

fibonacciList[10]

{1, 1, 2, 3, 5, 8, 13, 21, 34, 55}

Another useful way uses LinearRecurrence:

LinearRecurrence[{1, 1}, {1, 1}, 10]

{1, 1, 2, 3, 5, 8, 13, 21, 34, 55}

Hopefully these examples inspire you.

---

I now note that you request the sequence starting from zero. Most of these are easy to adapt or modify. The first one is simply:

Array[f, 10, 0]

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34}

For the second you may instead write:

fibonacciList2[n_] := Module[{x = 1}, NestList[x + (x = #) &, 0, n - 1]]

fibonacciList2[10]

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34}

The last one merely needs the proper seed:

LinearRecurrence[{1, 1}, {0, 1}, 10]

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34}

---

Finally, taking the question at face value you can modify your code to return fPrev rather than fNext to start from zero:

fibonacciSequence[n_] := 
 Module[{fPrev = 0, fNext = 1, i = 0}, 
  While[i++ < n, {fPrev, fNext} = {fNext, fPrev + fNext}];
  fPrev
 ]

Array[fibonacciSequence, 10, 0]

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34}

---

Addendum for rcollyer:

$fibList = {0, 1};
    fibonacciList[n_] /; n <= Length@$fibList := Take[$fibList, n]
    fibonacciList[n_] := $fibList =
  $fibList ~Join~ 
       Module[{x = $fibList[[-2]]}, 
        Rest@NestList[x + (x = #) &, $fibList[[-1]], n - Length@$fibList]]

Answer 2

This is probably defeating your professor's unspoken desire, but no one explicitly said you required a recursion. It may or may not entertain you to know Binet's formula. Without checking, I would guess that this approach is similar to how the built in function computes Fibonacci numbers. It is clearly computationally cheaper than any sort of recursion or nesting, and that would be noticeable deep into the sequence. This is a bit slower than the built in function, but it will do say the 3 millionth number pretty fast:

fibos[n_] := RootReduce@(((1 + Sqrt[5])/2)^n - ((1 - Sqrt[5])/2)^n)/Sqrt[5]

This could be made much shorter with some small modicum of effort. To get your table, implement it with something like:

Table[fibos[i], {i, 0, 15}]

Answer 3

f[n_]:=Union @@ NestList[{{0,1},{1,1}}.# &, {1, 1}, n]

EDIT

fib[n_]:=NestList[{{0,1},{1,1}}.# &, {0, 1}, n][[All,1]]

and MatrixPower method:

fn[n_]:=First[MatrixPower[{{1,1},{1,0},n-1].{1,0}]

Answer 4

In Mathematica 10.2 one can use the new function SequenceFoldList:

fib[n_] := SequenceFoldList[Plus, {0, 1}, ConstantArray[0, n - 1]];
fib[15]

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610}

Use SequenceFold to obtain just the last element.

Answer 5

Also taking your question at face value, but making the fix faster:

fibonacciSequence2[n_] := Module[
  {fPrev = 0, fNext = 1, i = 0, list = {0}},
  While[i++ < n,
   {fPrev, fNext} = {fNext, fPrev + fNext};
   list = {fPrev, list}
   ];
  Reverse@Flatten[list]
  ]

 fibonacciSequence2[5000] // Timing

This way of constructing a list has a name, it's called linked lists.

When I compare this with Mr. Wizard's fix for the 5000 first values, I get 0.015053 seconds instead of 21.764429. (Mr.Wizard did not intend speed and I get that. His other solutions are even faster than this, I checked the last one and it took just 0.008132.)

(Also this prints the list as requested)

Answer 6

This may do what you want:

Clear["`*"];
fibonacciSequence[n_] :=
 Module[{fPrev = 1, fNext = 0},
  Table[{fPrev, fNext} = {fNext, fPrev + fNext}, {n + 1}][[;; , 1]]
  ]

fibonacciSequence[15]
(* {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610} *)

---

a = 1; b = 0; Table[b = a + (a = b), {10}]
NestList[{+##, #} & @@ # &, {1, 1}, 10][[;; , 1]]
Nest[#~Append~Tr@#[[-2 ;;]] &, {1, 1}, 10]
Nest[# /. {a___, x_, y_} -> {a, x, y, x + y} &, {1, 1}, 10]
Nest[{1, 1}~Join~(Most@# + Rest@#) &, {1, 1}, 10]
Nest[Accumulate[{1, 0}~Join~#] &, {}, 5]

Answer 7

Tail recursive Fibonacci sequence generator

fiboSequence[n_, a_, b_] := fiboSequence[n - 1, b, Sow[a] + b]
fiboSequence[0, a_, b_] := Sow[a]
fiboSequence[n_] := Reap[fiboSequence[n, 0, 1]][[2, 1]]

fiboSequence[15]

$\ ${0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610}

Pattern matching Fibonacci sequence generator

fiboSequence2[n_] := 
 Quiet@ReplaceRepeated[{0, 1}, {x___, a_, b_} :> {x, a, b, a + b}, MaxIterations -> n - 1]

fiboSequence2[15]

$\ ${0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610}

Answer 8

For giggles, here is a contour integral method (based on Cauchy's formula) for computing the Fibonacci numbers:

Table[Round[Re[NIntegrate[1/((1 - z - z^2) z^n),
                          {z, 1/2, I/2, -1/2, -I/2, 1/2}]/(2 π I)]],
      {n, 10}]
   {1, 1, 2, 3, 5, 8, 13, 21, 34, 55}

Answer 9

For diversity reasons:

Table[a[i] /. 
  RSolve[{a[n] == a[n - 1] + a[n - 2], a[1] == 1, a[2] == 1}, a, n][[1]], 
  {i, 0, 15}]

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610}

or as @J.M. ironically remarked:

Array[DifferenceRoot[
  Function[{a, n}, {a[n] == a[n - 1] + a[n - 2], a[1] == 1, a[2] == 1}]], 16, 0]

Answer 10

Another natural approach is to use the built-in RecurrenceTable

RecurrenceTable[{f[n] == f[n - 1] + f[n - 2], f[1] == 1, 
  f[0] == 0}, f, {n, 0, 15}]
(* {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610} *)