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

Tomorin
Release: 2018-08-17 17:53:32
Original
2374 people have browsed it

Inside the function, other functions can be called. If a function calls itself internally, the function is arecursive 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 arecursive way:

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

The above is a recursive function. You can try:

>>> fact(1) 1 >>> fact(5) 120 >>> fact(100) 933262154439441526816992388562667004907159682643816214685 92963895217599993229915608941463976156518286253697920827223 758251185210916864000000000000000000000000
Copy after login

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 "", line 1, in  File "", line 4, in fact ... File "", line 4, in fact RuntimeError: maximum recursion depth exceeded in comparison
Copy after login


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!

Related labels:
source:php.cn
Statement of this Website
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
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!