# Chapter 05: Induction and Recursion¶

## Example 01: Page 346¶

In [1]:
#to compute the recursive functions
def f(n):

if n==0:
return 3
else:
n=n-1
result=2*f(n)+3 #recursive call
return result
for num in range(1,5):
r=f(num)
print "The value of f(",num,") is",r #Prints the result for individual instance

The value of f( 1 ) is 9
The value of f( 2 ) is 21
The value of f( 3 ) is 45
The value of f( 4 ) is 93


## Example 01: Page 361¶

In [2]:
#To compute the factorial of a given number using recursion
def factorial(n):
if n==0:
return 1
else:
return n*factorial(n-1) #recursive function call
num=input("Enter a number whose factorial is to be found");
print "The factorial of",num,"is",factorial(num);

Enter a number whose factorial is to be found4
The factorial of 4 is 24


## Example 02: Page 361¶

In [3]:
#To compute power using recursive algorithm
def power(a,n):
if n==0:
return 1
else:
return a*power(a,n-1) #recursive call algorithm
num=input("Enter the number");
p=input("Enter the power");
print "The value of",num,"to the power",p,"is",power(num,p);

Enter the number5
Enter the power4
The value of 5 to the power 4 is 625


## Example 03: Page 362¶

In [5]:
#To compute gcd using modular recursion
def gcd(a,b):
if a==0:
return b
else:
return gcd(b%a,a) #recursive call

num1=input("Enter the first number")
num2=input("Enter the second number")
print "The gcd of",num1,",",num2,"is",gcd(num1,num2)

Enter the first number5
Enter the second number8
The gcd of 5 , 8 is 1


## Example 04: Page 362¶

In [4]:
#To compute mpower function using recursion
def mpower(b,n,m):
if n==0:
return 1
else:
if n%2==0:
return ((mpower(b,n/2,m))**2) % m #recursive call
else:
return ((mpower(b,n/2,m)**2)%m*(b%m))%m #recursive call
number=input("Enter the number")
power=input("Enter the power")
modulo=input("Enter the modulo number");
print "The answer of mpower(",number,",",power,",",modulo,") is",mpower(number,power,modulo)

Enter the number2
Enter the power5
Enter the modulo number3
The answer of mpower( 2 , 5 , 3 ) is 2


## Example 09: Page 367¶

In [5]:
def msort2(x): #function for merge sort
if len(x) < 2:
return x
result = []
mid = int(len(x)/2) #divides the elements into halves
y = msort2(x[:mid])
z = msort2(x[mid:])
while (len(y) > 0) and (len(z) > 0):
if y[0] > z[0]:
result.append(z[0]) #merges to append the elements
z.pop(0)
else:
result.append(y[0])
y.pop(0)
result += y
result += z
return result
l=[]
r=[]
l=raw_input("enter the numbers to be merge sorted").split(",")
r=msort2(l)
print "Ther Merge sort is", r

enter the numbers to be merge sorted8,2,4,6,9,7,10,1,5,3
Ther Merge sort is ['1', '10', '2', '3', '4', '5', '6', '7', '8', '9']