-base cases
fibonacci(0)=0
fibonacci(1)=1
-recursive case
fibonacci(n) = fibonacci(n-1)+fibonacci(n-2)
n > 1
A procedure, fibonacci, that takes a natural number as its input, and returns the value of that fibonacci number.
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
fibonacci has interesting feature below
fibo(x) = fibo(x-n-1)
More faster fibonacci procedure using for loop.
def fibonacci(n):
current = 0
after = 1
for i in range(0, n):
current, after = after, current + after
return current
mass_of_earth = 5.9722 * 10**24
mass_of_rabbit = 2
n = 1
while fibonacci(n) * mass_of_rabbit < mass_of_earth:
n = n + 1
print n, fibonacci(n)
- Ranking web pages as popularity
popularity(p) = # of people who are friends with p
popularity(p) = Σ popularity(f), f E friends of p
def popularity(p):
score = 0
for f in friends(p):
score = score + popularity(f)
return score
