**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()
```

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()
```

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()
```

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()
```

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()
```

In [ ]:

```
```

In [ ]:

```
```