Chapter 05: Induction and Recursion

Example 01: Page 346

#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

#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

#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

#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

#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

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']