Python recursive function definitions and usage examples

This article illustrates the definition and usage of Python recursive function. To share for your reference, specific as follows:

Recursive function

Inside a function, you can call other functions. If a function calls itself internally, it is a recursive function.

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

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

Therefore, fact(n) can be expressed as n * fact(ES21en-1), only n=1 requires special treatment.
So fact(n) is written recursively as follows:

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

It's a recursive function up here. Try:

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

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

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

Recursive functions have the advantage of being simple to define and logical. In theory, all recursive functions can be written as loops, but the logic of loops is not as clear as that of recursion.

Using recursive functions requires care to prevent stack overflow. In computers, function calls are implemented using the stack (stack) data structure. Each time a function call is made, the stack adds 1 stack frame and each time the function returns, the stack subtracts 1 stack frame. Because the stack size is not infinite, too many recursive calls result in stack overflow. Try fact(10000).

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

For more information about Python, please refer to Python Data Structure and Algorithm Tutorial, Python Socket Programming Skills Summary, Python Function Using Skills Summary, Python String Operation Skills Summary, Python Introduction and Advanced Classic Tutorial and Python File and Directory Operation Skills Summary.

I hope this article has been helpful for Python programming.