Some Programs involving Recursion

We can find a^b using recursion.The code is..

def power(a, b):
if (b == 0):
return 1
else:
a=a*power(a, b-1)
return a

print power(3, 9)


We can optimise the above program and reduce the time complexity.
Here is the code for that..

def power(a, b):
if(b == 0):
return 1
else:
if(b%2 == 0):
v = power(a, b/2)
return v**2
else:
v = power(a, (b-1)/2)
return a*v**2

print power(3, 5)


Next we can move on to finding the nth element of Fibonacci series.
For that we have a recursive code..

def fib(n):
if n<2 :
return n
else:
return fib(n-1)+fib(n-2)

print fib(6)


We can optimise the above code using the technique of memorisation.
Then the code will be..

def fib(n):
if not n in memory:
memory[n] = fib(n-1) + fib(n-2)
return memory[n]

memory={0:0,1:1}
print fib (250)