Home >Backend Development >Python Tutorial >Is Python recursive algorithm difficult? Detailed examples of Python recursive functions

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

Tomorin
TomorinOriginal
2018-08-17 17:53:322475browse

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!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn