# 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 [ ]: