Is Python recursive algorithm difficult? Detailed examples of Python recursive functions

Inside the function, other functions can be called. If a function calls itself internally, the function is a recursive function.

For example, let's calculate the factorial n! = 1 x 2 x 3 x ... x n, expressed by the function fact(n), it can be seen:

fact(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fact(n-1) x n

So, fact(n) can be expressed For n x fact(n-1), only n=1 requires special treatment.

So, fact(n) is written in a recursive way:

def fact(n):
    if n==1:     
       return 1
    return n * fact(n - 1)

The above is a recursive function. You can try:

>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
933262154439441526816992388562667004907159682643816214685
92963895217599993229915608941463976156518286253697920827223
758251185210916864000000000000000000000000

If we calculate fact(5), we can see the calculation process as follows according to the function definition:

===> 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 advantages of recursive functions are simple definition and clear logic. Theoretically, all recursive functions can be written in a loop, but the logic of loops is not as clear as recursion.

When using recursive functions, care must be taken to prevent stack overflow. In computers, function calls are implemented through the data structure of the stack. Whenever a function call is entered, a stack frame is added to the stack. Whenever a function returns, a stack frame is subtracted from the stack. Since the size of the stack is not infinite, too many 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 above is the detailed content of Is Python recursive algorithm difficult? Detailed examples of Python recursive functions. For more information, please follow other related articles on the PHP Chinese website!