Recursion

Acknowledgement : the contents of this notebook are partially based on the book "Starting Out with Python (3rd Edition)".

A recursive function is a function that calls itself.

In [ ]:
# this program has a recursive function. 
# It runs forever.
def main():
    message()
    
def message():
    print('This is a recursive function.')
    message()
    
# call the main function
main()
In [1]:
# this program has a recursive function.
# This recursive function has a stopping condition. 
def main():
    message(5)
    
def message(times):
    if times > 0:
        print('This is a recursive function.')
        message(times-1)
    
# call the main function
main()
This is a recursive function.
This is a recursive function.
This is a recursive function.
This is a recursive function.
This is a recursive function.

Problem solving with recursion

A problem can be solved with recursion if it can be broken down into smaller problems that are identical in structure to the overall problem.

In [2]:
# this program uses recursion to calculate the factorial of a number

def main():
    # get a number from the user.
    number = int(input('Enter a nonnegative integer : '))
    
    # get the factorial of the number.
    fact = factorial(number)
    
    # display the factorial
    print('The factorial of ',number,'is',fact)
    
# this is a recursive function to calculate the factorial
def factorial(num):
    if num == 0:
        return 1
    else:
        return num * factorial(num-1)
    
# call the main function
main()
Enter a nonnegative integer : 10
The factorial of  10 is 3628800

Examples of recursive algorithms

In [3]:
# summing with recursion
In [4]:
def main():
    # create a list of numbers
    numbers = [1,2,3,4,5,6,7,8,9]
    
    # get the sum of the items at indexes 2 through 5
    my_sum = range_sum(numbers,2,5)
    
    # display the sum
    print('The sum of items 2 through 5 is',my_sum)
    
# function to perform sum over a range
def range_sum(num_list,start,end):
    if start > end:
        return 0
    else:
        return num_list[start] + range_sum(num_list,start+1,end)
    
# call the main function
main()
The sum of items 2 through 5 is 18
In [5]:
# the Fibonacci series
In [6]:
def main():
    print('The first 10 numbers in the Fibonacci series are:')
    
    for number in range(1,11):
        print(fib(number))
        
# the fib function returns the nth number 
# in the Fibonacci series
def fib(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
        
# call the main function
main()
The first 10 numbers in the Fibonacci series are:
1
1
2
3
5
8
13
21
34
55
In [7]:
# finding the greatest common divisor (GCD)
# The GCD of two positive integers x and y is determined as follows:
# if x can be evenly divided by y, then gcd(x,y) = y
# Otherwise, gcd(x,y) = gcd(y,remainder of x/y)
In [8]:
def main():
    # get two numbers
    num1 = int(input('Enter an integer : '))
    num2 = int(input('Enter another integer : '))
    
    # display the GCD
    print('The greatest common divisor of the two numbers is',gcd(num1,num2))
    
# the gcd function returns the 
# greatest common divisor of the two numbers.
def gcd(x,y):
    if x % y == 0:
        return y
    else:
        return gcd(x,x % y)
    
# call the main function
main()
Enter an integer : 15
Enter another integer : 60
The greatest common divisor of the two numbers is 15
In [ ]:
 
In [ ]: