Recursion in Python refers to the concept when a function is called by itself one or more times.
Syntax
def fun():
// statements
fun()
Consider a scenario where we want calculate the factorial of n = 5, let’s see how it goes :
factorial(5) :
-> 5 * factorial(4)
–> 5 * 4 * factorial(3)
—> 5 * 4 * 3 * factorial(2)
—-> 5 * 4 * 3 * 2 * factorial(1)
—–> 5 * 4 * 3 * 2 * 1 = 120
Here, you must be able to catch the common pattern.
So, recursive formula to calculate factorial of any number ‘n’ is given as :
factorial(n) = n * factorial(n-1)
Here, function factorial() is calling itself with different values of ‘n’.
One thing to note is that every recursive function requires a break-down condition. A break-down condition is a condition which breaks down the program flow once intended purpose is completed.
If recursive function, does not have any break-down condition then, it will become an infinite loop.
Program : To calculate the factorial of a given number using recursion
def factorial(n):
if n == 1: # break-down condition
return 1
else:
return n * factorial(n-1)
print(factorial(5))
Above function factorial() evaluates the factorial of 5.
if n == 1 :
Above line is a break-down condition. This means that program flow will stop when ‘n’ becomes 0 and final value is returned.
Let’s try to break this :
Recursion has two phases :
1. Winding Phase : This phase runs until desired condition is fulfilled.
2. Unwinding Phase : Once winding phase gets over, control is transferred back to original call, this is unwinding phase.
Types of Recursion in Python
Recursion in Python is of two types :
1. Direct Recursion
2. Indirect Recursion
Let’s explore them one-by-one
Direct Recursion
Direct Recursion is a type of recursion in which a function explicitly calls itself, usually with a different set of values. It is further divided into 3 types :
1. Tail Recursion
2. Non Tail Recursion
3. Tree Recursion
Tail Recursion
Tail Recursion occurs if a recursive function calls itself and the function call is the last statement to be processed in the function before returning having reached the base case. After processing the call, function returns control back to the parent function call.
Program : To print counting from 1 to 10 with the help of tail recursion.
def counting(n):
if n == 11: # break-down condition
return
else:
print(n)
counting(n+1)
counting(1)
O/P
1
2
3
4
5
6
7
8
9
10
In the above code, function counting() has a recursive call as a last statement. Here, the program will terminate when
n = 11, this is the break-down condition or also known as base condition of a program.
Order of Execution : print(1) -> counting(1) -> print(2) -> counting(2) -> print(3) -> counting(3) -> print(4) -> counting(4) -> print(5) -> counting(5) -> print(6) -> counting(6) -> print(7) -> counting(7) -> print(8) -> counting(8) -> print(9) -> counting(9) -> print(10) -> counting(10) -> n == 11
Non Tail Recursion
Non Tail Recursion occurs if a recursive function calls itself and the function call is not the last statement to be processed in the function. In non tail recursion, there are some operations executed even after the recursive call.
Program : To print counting from 1 to 10 with the help of non tail recursion.
def counting(n):
if n == 0: # break-down condition
return
else:
counting(n-1) # recursive call is not the last statement
print(n)
counting(10)
O/P
1
2
3
4
5
6
7
8
9
10
In the above code, function counting() has a recursive call but not as a last statement. Here, the program will terminate when
n = 0, this is the break-down condition or also known as base condition of a program.
Order of execution :
counting(10) -> counting(9) -> counting(8) -> counting(7) -> counting(6) -> counting(5) -> counting(4) -> counting(3) -> counting(2) -> counting(1) -> n == 0 condition satisfies -> Now print statement will come into picture.
counting(1) will return 1, counting(2) will return 2, counting(3) will return 3 and so on.
Tree Recursion
Tree Recursion in Python is a type of recursion in which a function is called two or more times in the same function.
Program : To print n-th term of fibonacci series (1 1 2 3 5 8 13 21 …) in Python using Tree Recursion.
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(4))
O/P : 3
Order of Execution : Please refer to the below image in order to trace the execution
Indirect Recursion
Indirect Recursion is a type of recursion where two or more functions are involved in mutual-invocation. This means that, if function fun1() calls another function fun2() and, fun2() calls fun1() again, then this is termed as indirect recursion.
def fun1():
# statements
fun2()
def fun2():
# statements
fun1()
Program : To implement Indirect Recursion
def fun1(a):
if a % 2 == 0:
print(a)
return
a += 1
fun2(a)
def fun2(a):
if a % 2 == 0:
print(a)
return
a += 2
fun1(a)
fun1(11)
O/P : 12
In the above program, our task is to terminate the program when ‘a’ becomes even.
Function fun1() increments value by 1 then calls fun2() and function fun2() increments value by 2 then calls fun1().
Application of Recursion in Python
Recursive algorithms are usually shorter and are used to solve many complex real world problems. Some of them are :
- Postfix, Prefix, Infix Conversion
- Tower of Hanoi
- Parenthesis Matching
- N-Queen’s Problem
- Depth First Search, Breadth First Search
Recursive Algorithms have higher runtime complexities.
Difference between Iteration and Recursion
Recursion | Iteration |
Recursion achieves repetition through repeated function calls. | Iteration explicitly uses repeated structure. |
Recursion terminates when base case is recognized. | Iteration terminates when loop condition fails. |
Recursion returns a value to the calling function. | Iteration does not return any value. |
Recursion makes a code smaller. | Iteration makes a code larger. |
Recursion is a slower process than iteration. | Iteration is faster. |
That’s all about Recursion in Python.