Example analysis of the definition and usage of Python recursive functions

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)

The above is a recursive function. You can try:

>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L

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 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))

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!