Inside a function, you can call other functions. If a function calls itself internally, this function is called a recursive function.
For example, let’s calculate the factorial n! = 1 x 2 x 3 x … x n, denoted by the function fact(n). We can see:
fact(n)=n!=1×2×3×⋅⋅⋅×(n−1)×n=(n−1)!×n=fact(n−1)×n
So, fact(n) can be expressed as n x fact(n-1), with a special case needed only when n = 1.
Thus, fact(n) written recursively is:
def fact(n):
if n == 1:
return 1
return n * fact(n - 1)
The above is a recursive function. You can try it:
>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
If we calculate fact(5), we can see the computation process based on the function definition as follows:
=> fact(5)
=> 5 * fact(4)
=> 5 * (4 * fact(3))
=> 5 * (4 * (3 * fact(2)))
=> 5 * (4 * (3 * (2 * fact(1))))
=> 5 * (4 * (3 * (2 * 1)))
=> 5 * (4 * (3 * 2))
=> 5 * (4 * 6)
=> 5 * 24
=> 120
The advantage of recursive functions is their simple definition and clear logic. Theoretically, all recursive functions can be written iteratively (using loops), but the logic of loops is often less clear than that of recursion.
When using recursive functions, you need to be careful to prevent stack overflow. In computers, function calls are implemented using a data structure called a stack. Each time a function call is made, a new stack frame is pushed onto the stack. Each time a function returns, a stack frame is popped off the stack. Since the size of the stack is not infinite, excessive recursive calls will cause stack overflow. You can try fact(1000):
>>> fact(1000)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 4, in fact
...
File "<stdin>", line 4, in fact
RuntimeError: maximum recursion depth exceeded in comparison
The solution to recursive call stack overflow is tail recursion optimization. In fact, tail recursion is equivalent in effect to looping; therefore, it’s also acceptable to think of a loop as a special type of tail recursive function.
Tail recursion means that when a function returns, it calls itself, and the return statement does not contain any expression. This allows the compiler or interpreter to optimize tail recursion so that no matter how many times the recursion calls itself, it only occupies a single stack frame, thus preventing stack overflow.
The fact(n) function above is not tail-recursive because return n * fact(n - 1) includes a multiplication expression. To convert it to a tail-recursive style requires a bit more code, mainly to pass the product of each step into the recursive function:
def fact(n):
return fact_iter(n, 1)
def fact_iter(num, product):
if num == 1:
return product
return fact_iter(num - 1, num * product)
As you can see, return fact_iter(num - 1, num * product) only returns the recursive function itself. num - 1 and num * product are evaluated before the function call and do not affect the call itself.
The call sequence for fact(5), which corresponds to fact_iter(5, 1), is as follows:
=> fact_iter(5, 1)
=> fact_iter(4, 5)
=> fact_iter(3, 20)
=> fact_iter(2, 60)
=> fact_iter(1, 120)
=> 120
During a tail-recursive call, if optimized, the stack does not grow. Therefore, no number of calls will cause a stack overflow.
Unfortunately, most programming languages do not perform tail recursion optimization, and the Python interpreter is no exception. Therefore, even if you rewrite the fact(n) function above in a tail-recursive style, it will still cause a stack overflow.
The advantage of using recursive functions is their simple and clear logic. The disadvantage is that excessively deep calls can lead to stack overflow.
Languages that optimize for tail recursion can prevent stack overflow through tail recursion. Tail recursion is actually equivalent to looping; programming languages without loop statements can only implement loops through tail recursion.
The standard Python interpreter does not perform tail recursion optimization, so any recursive function is subject to the problem of stack overflow.