Module 1, Practical 11¶
In this practical we will work with recursive functions.
Recursive functions¶
Recursion is the process of defining something in terms of itself. A physical world example would be to place two parallel mirrors facing each other. Any object in between them would be reflected recursively.
In Python, we know that a function can call other functions. It is even possible for the function to call itself. These types of construct are termed as recursive functions.
The following image shows the working of a recursive function called recurse.
Following is an example of a recursive function to find the factorial of an integer.
[ ]:
def factorial(x):
"""This is a recursive function
to find the factorial of an integer"""
if x == 1:
return 1 # base case
else:
return (x * factorial(x-1))
num = 3
print("The factorial of", num, "is", factorial(num))
Output: The factorial of 3 is 6
When we call factorial with a positive integer, it will recursively call itself by decreasing the number. Each function multiplies the number with the factorial of the number below it until it is equal to one. This recursive call can be explained in the following steps.
Our recursion ends when the number reduces to 1. This is called the base case. While defining a recursive function, there must be at least one base case for which we know the result. Then every successive recursive function call must bring it closer to the base case. This is required so that eventually the recursive calls terminate. Otherwise, the function will never terminate and we will get out of memory error.
The recursion is very similar to a loop where the function is called in every iteration. That’s why we can almost always use loops as a replacement for Python recursion function.
Example (Fibonacci series)
The Fibonacci series is the sequence of numbers where each number is the sum of two preceding numbers. For example 1, 1, 2, 3, 5, 8, 13, 21, .... The following codes generate the Fibonacci series by iteration (loops) and by recursion.
[ ]:
def fibonacci(n):
""" Returns Fibonacci Number at nth position using loop"""
if n == 0:
return 0
if n == 1:
return 1
i1 = 0
i2 = 1
num = 1
for x in range(1, n):
num = i1 + i2
i1 = i2
i2 = num
return num
for i in range(10):
print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13 21 34
[ ]:
def fibonacci(n):
""" Returns Fibonacci Number at nth position using recursion"""
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
for i in range(10):
print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13 21 34
Advantages of Recursion
Recursive functions make the code look clean and elegant.
A complex task can be broken down into simpler sub-problems using recursion.
Sequence generation is easier with recursion than using some nested iteration.
Disadvantages of Recursion
Sometimes the logic behind recursion is hard to follow through.
Recursive calls are expensive (inefficient) as they take up a lot of memory and time.
Recursive functions are hard to debug.
Exercise¶
The Python application TestMyMath.py allow to test the implementation of a set of recursive mathematical functions implemented in the Python module MyMath.py imported in the application.
[ ]:
import MyMath # this imports the module with all the recursive functions
# main program to test the recursive implementations
# variables used during the computations
x = 3
y = 5
u = 1
n = 0
bigN = 12153
v = [1, 0, -3, 4, 10] # array with 5 elements...
print("Factorial of", y, "is:", MyMath.factorialIt(y), "(iterative implementation)")
print("Factorial of", y, "is:", MyMath.factorialRec(y), "(recursive implementation)\n")
print(x, "+", y, "=", MyMath.RecursiveSum(x,y))
print(x, "+", -y, "=", MyMath.RecursiveSum(x,-y))
print(x, "-", y, "=", MyMath.RecursiveDiff(x,y))
print(x, "-", -y, "=", MyMath.RecursiveDiff(x,-y))
print(x, "*", y, "=", MyMath.RecursiveProd(x,y))
print(x, "*", -y, "=", MyMath.RecursiveProd(x,-y))
print(x, "^", y, "=", MyMath.RecursivePower(x,y))
print(x, "^", -y, "=", MyMath.RecursivePower(x,-y))
print(x, "^", u, "=", MyMath.RecursivePower(x,u))
print(x, "^", n, "=", MyMath.RecursivePower(x,n))
print("\nMin of", v, "=", MyMath.RecursiveMin(v))
print("Max of", v, "=", MyMath.RecursiveMax(v))
print("\nThe highest digit of", bigN, "is:", MyMath.RecursiveMaxDigit(bigN))
print('\nNumber of "1" in', bigN, ":", MyMath.RecursiveCountDigit(1,bigN))
print('Number of "3" in', bigN, ":", MyMath.RecursiveCountDigit(3,bigN))
print('Number of "7" in', bigN, ":", MyMath.RecursiveCountDigit(7,bigN))
print("\nThe sum of the elements of", v, "is", MyMath.RecursiveArraySum(v))
The MyMath module provides a wide range of recursive functions. Some of them implement classical mathematical functions:
[ ]:
def RecursiveSum(a,b):
"""RECURSIVE function to compute a+b."""
if b < 0:
return RecursiveDiff(a,-b)
if b == 0:
return a
else:
return 1 + RecursiveSum(a,b-1)
Other functions compute more complex operations and can make use of private support functions to extend the function signature and make iteration possible:
[ ]:
def RecursiveMin(v):
"""RECURSIVE function to compute min(v)."""
return __RecursiveMin(v,1,v[0])
def __RecursiveMin(v,i,min):
"""RECURSIVE private function to compute min(v)."""
# min stores the current min value, i stores the next element of v to check...
if i == len(v):
return min
if v[i] < min:
return __RecursiveMin(v,i+1,v[i])
return __RecursiveMin(v,i+1,min)
To complete the exercise, complete all the missing implementations of MyMath.py. If the module will be properly completed, TestMyMath.py will provide the following output:
Factorial of 5 is: 120 (iterative implementation)
Factorial of 5 is: 120 (recursive implementation)
3 + 5 = 8
3 + -5 = -2
3 - 5 = -2
3 - -5 = 8
3 * 5 = 15
3 * -5 = -15
3 ^ 5 = 243
3 ^ -5 = 0.00411522633744856
3 ^ 1 = 3
3 ^ 0 = 1
Min of [1, 0, -3, 4, 10] = -3
Max of [1, 0, -3, 4, 10] = 10
The highest digit of 12153 is: 5
Number of "1" in 12153 : 2
Number of "3" in 12153 : 1
Number of "7" in 12153 : 0
The sum of the elements of [1, 0, -3, 4, 10] is 12
Show/Hide Solution