What is recursion?
Recursion is the process of repeating items or operations in a self-similar way.
In Python, if your program allows you to call a function inside the same function, then it is called a Recursive Function.
Recursion is an advanced and to some extent an unused topic. However, it is useful to know about this technique, as it allows you to deal with arbitrary structures and unpredictable shapes.
Example of Recursive Functions
Let’s calculate the factorial of a number in Python.
Ideally, you would do this by using a for loop.
num = 5 factorial = 1 for i in range(1, num+1): factorial *= i print(factorial)
Pretty straightforward, right?
You can also do it using Recursion.
Code - Using Recursion
def factorial(x): if x == 1: return 1 else: # call the function again return (x * factorial(x-1)) num = 5 print(factorial(num))
When you call this function with a positive integer, it will keep calling itself recursively by decreasing the number.
Each function call multiplies the number with the factorial of the number until it is equal to one.
factorial(5) # First function call 5 * factorial(4) # 2nd function call with 4 5 * 4 * factorial(3) # 3rd function call with 3 5 * 4 * 3 * factorial(2) # 4th function call with 2 5 * 4 * 3 * 2 * factorial(1) # 5th function call with 1 5 * 4 * 3 * 2 * 1 120
Basically, when the
factorial() function returned 1, the recursion stopped. This is called Base Condition.
Every recursive function should have a base condition, otherwise, the recursion continues infinitely.
The Python interpreter limits the depths of recursion to help avoid infinite recursions. By default, the maximum depth of recursion is 1000. If the limit is crossed, it results in
Advantages of Recursion
- Recursive functions look clean and elegant.
- It can break down complex problems into multiple small problems using recursion.
Disadvantages of Recursion
- Can be difficult to understand.
- Recursion is expensive.
- They are also hard to debug.