Python Recursion (Recursion)

In this article, you will learn how to create recursive functions (functions that call themselves).

What is recursion in Python?

Recursion is the process of defining something in terms of itself.

An example in the physical world is placing two parallel mirrors facing each other. Any object between them will be recursively reflected.

Python recursive function

In Python, we know aFunctionA function can call other functions. A function may even call itself. These types of constructions are called recursive functions.

The following is an example of a recursive function to find the factorial of an integer.

The factorial of a number is from16,6）is1 * 2 * 3 * 4 * 5 * 6 = 720.

Recursive function example

def calc_factorial(x):
　　　　"""This is
　　　　Recursive function for calculating the factorial of an integer"
　　　　if x ==　1:
　　　　　　　　return　1
　　　　else:
　　　　　　　　return (x　*　calc_factorial(x-1))
num =　4
print("The factorial of", num, "is", calc_factorial(num))

In the above example, it calc_factorial() is a recursive function that calls itself.

When we call this function with a positive integer, it will recursively call itself by reducing the number.

Each function multiplies the number by the factorial of the number below it until it equals1. The following steps can explain this recursive call.

calc_factorial(4) #　1st call with　4
4　*　calc_factorial(3) #　2nd call with　3
4　*　3　*　calc_factorial(2) #　3rd call with　2
4　*　3　*　2　*　calc_factorial(1) #　4th call with　1
4　*　3　*　2　*　1　　　　　　　　　　　　　　　　　　# return from　4th call as number=1
4　*　3　*　2　　　　　　　　　　　　　　　　　　　　　　# return from　3rd call
4　*　6　　　　　　　　　　　　　　　　　　　　　　　　　　# return from　2nd call
24　　　　　　　　　　　　　　　　　　　　　　　　　　　　　# return from　1st call

When the number is reduced to1When this condition is met, recursion ends. This is called the basic condition.

Each recursive function must have a basic condition to stop recursion, otherwise the function will call itself infinitely.

The Python interpreter limits the depth of recursion to help avoid infinite recursion, which can lead to stack overflow.

By default, the maximum recursion depth is 1000. If the limit is exceeded, the result will be RecursionError. Let's look at such a condition.

def recursor():
　　　　recursor()
recursor()

Output result

Traceback (most recent call last):
　　File "<string>", line　3, in <module>
　　File "<string>", line　2, in a
　　File "<string>", line　2, in a
　　File "<string>", line　2, in a
　　[Previous line repeated　996　more times]
RecursionError: maximum recursion depth exceeded

Advantages of recursion

1. Recursive functions make the code look clean and tidy.

2. Using recursion can break down complex tasks into simpler subproblems.

3. Compared with nested nesting, recursion is easier to generate sequences.

Disadvantages of recursion

1. Sometimes, the logic behind recursion is difficult to follow.

2. Recursive calls are expensive (inefficient) because they consume a large amount of memory and time.

3. Recursive functions are difficult to debug.