Recursion in Python
I worked through recursion in the Computational Statistics in Python tutorial, getting up to speed on Python, and although this code is similar to the tutorial, I did try to 'make it mine':
# Recursion
"""http://people.duke.edu/~ccc14/sta-663/FunctionsSolutions.html#recursion"""
# Correct Example
def fibonacci(n):
if n==0 or n==1:
return 1
else:
return fibonacci(n-1) + fibonacci (n-2)
[fibonacci(n) for n in range(10)]
def fibonacciWithCache(n, cache={0:1, 1:1}):
try:
return cache[n]
except:
cache[n] = fibonacci(n-1) + fibonacci (n-2)
return cache[n]
[fibonacciWithCache(n) for n in range(10)]
# Correct Example
def factorial(n):
if n==0:
return 1
else:
return n * factorial(n-1)
# Correct Example, with caching
def factorialWithCache(n, cache={0:1}):
try:
return cache[n]
except KeyError:
cache[n] = n * factorial(n-1)
return cache[n]
#5! = 1*2*3*4*5
[factorial(n) for n in range(100)]
[factorialWithCache(n) for n in range(100)]
def FibonacciNonRecursive(n):
"""Fib without recursion.
Note: uses assignment reversal"""
a, b = 0, 1
for i in range(1, n+1):
a, b = b, a+b
return b
[FibonacciNonRecursive(i) for i in range(1)]
Comments
Post a Comment