Kenneth: /* Recursion */

2014-06-25T21:58:58Z

Recursion

New page

== Sequence ==

Fibonacci sequence is a sequence where each subsequent number is the sum of the previous two. [http://en.wikipedia.org/wiki/Fibonacci_number]

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

http://upload.wikimedia.org/wikipedia/commons/thumb/9/93/Fibonacci_spiral_34.svg/180px-Fibonacci_spiral_34.svg.png

== Math ==

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

http://upload.wikimedia.org/math/0/c/e/0cebc512d9a3ac497eda6f10203f792e.png

with seed values

http://upload.wikimedia.org/math/4/3/d/43d30dc03ffec0a82d4471f1009ef519.png

or

http://upload.wikimedia.org/math/a/9/2/a92c5f0981136ba333124cdfe6d3c3ce.png

[[Category:Math]]

== Python ==

=== Loop ===

<pre>
def fib(count):
a = 0
b = 1
print b
for i in range(count):
c = a + b
print c
a = b
b = c

fib(100)
</pre>

=== Recursion ===

Recursion:
<pre>
def fib(count, last=0, current=1):
if count < 1: return
print current
fib(count-1, current, last+current)

fib(100)
</pre>

---

WARNING: It appears the recursion will fail after about 999 recursive calls with:
RuntimeError: maximum recursion depth exceeded

Tested with (until it blew up):
<pre>
def fib(count=1, last=0, current=1):
print count
fib(count+1, current, last+current)

fib()
</pre>

Fibonacci Sequence - Revision history

Kenneth: /* Recursion */