Example analysis of the definition and usage of Python recursive functions

黄舟
Release: 2017-06-04 10:12:41
Original
1666 people have browsed it

This article mainly introduces the Pythonrecursive functiondefinition and usage, and analyzes the principles, implementation techniques and related Notes of Python recursive functions in combination with specific examples. ##, friends in need can refer to

The examples in this article describe the definition and usage of Python recursive functions. Share it with everyone for your reference, the details are as follows:

Recursive function

Within the function, you can call other functions. A function is recursive if it calls itself internally.

For example, let’s calculate the factorial n! = 1 * 2 * 3 * ... * n, represented 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 * fact(n-1), only when n=1 requires special treatment.

So, fact(n) is written recursively:

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)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L
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
Copy after login

The advantages of recursive functions are simple definition and clear logic. Theoretically, all recursive functions can be written in the form of

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 layer of stack frames is added to the stack. Whenever a function returns, a layer of stack frames 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 calculating fact(10000).

def digui(n):
  sum = 0
  if n<=0:
    return 1
  else:
    return n*digui(n-1)
print(digui(5))
Copy after login

The above is the detailed content of Example analysis of the definition and usage 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
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template