Summary of python Recursive Related Knowledge

Directory 1. Finding factorial in a non-recursive way
2. Find factorial recursively
1. What is recursion?
2. Solve factorial recursively
3. Summary

I always feel quite tall when I hear recursion. Why? Because I am unfamiliar with it, let's remember what recursion is today.

But don't worry, let's look at a problem: find the factorial of 10 (10!) .

To find the factorial of x, we actually multiply it from 1 to x in turn. Then the factorial of 10 is 1*2*3*4*5*6*7*8*9*10

1. Find factorial in a non-recursive way

If we have not been exposed to recursion, how can we solve such a problem?

The simplest and rudest way is to get the result directly from print (1*2*3*4*5*6*7*8*9*10), and the result is 3628800.

But this way is obviously not what we want, so we can try to solve it with for loop.

def factorial(n):
 """
 n  Is the number of factorial required 
 """
 result = n
 for i in range(1, n):
  result *= i

 return result

if __name__ == '__main__':
 print(factorial(10))

2. Find factorial recursively

1. What is recursion?

I believe everyone has heard such a story:

Once upon a time, there was a mountain, and there was a temple in the mountain. There was an old monk telling stories in the temple. What was he talking about?
Once upon a time, there was a mountain, and there was a temple in the mountain. There was an old monk telling stories in the temple. What was he talking about?
Once upon a time, there was a mountain, and there was a temple in the mountain. There was an old monk telling stories in the temple. What was he talking about?
...

In fact, this is recursion. To put it bluntly, it is to quote yourself.
Then, when recursion is used in a function, it can be like this:

def factorial():
 factorial() 

if __name__ == '__main__':
 factorial()

Calling a function factorial And then continue to call in the function factorial Like story 1 above, you can recursively go on endlessly.
Until the old monk who told the story was tired and dizzy, and the computer overflowed and went down.

However, the important point is that recursion is only a way to solve the problem. For example, the factorial above is solved by for loop 1.

2. Solve factorial recursively

If you want to use recursion to solve the factorial problem above, you can take another step to understand the overall idea of recursion.

The whole idea of recursion is to decompose a big problem into small problems until there is no way to continue decomposing the problem, so we can solve the problem again.
Then, the recursive function must satisfy two conditions:

Baseline condition: The problem can be decomposed into the minimum problem. When the baseline condition is met, recursion is no longer carried out Recursive condition: continuing to decompose the problem

This idea can be used to try to solve the factorial problem in a recursive way.

10! = 10 * 9! # 10 The factorial of can actually be regarded as 10 * 9 Factorial of 
9! = 9 * 8!  # 9 The factorial of can be regarded as 9 * 8 Factorial of 
8! = 8 * 7!
...
2! = 2 * 1!
1! = 1

As you can see, when you finally decompose to 1, you can't continue decomposition, so 1 is the baseline condition.

def factorial(n):
 #  Baseline condition, when met, is no longer recursive 
 if n == 1:
  return 1

 #  Recursive condition, when n Not equal to 1 Continue recursion 
 return n * factorial(n - 1)

if __name__ == '__main__':
 print(factorial(10))

3. Summary

Recursion: It is only a way to solve the problem, but it must be used Recursive function: That is, the function calls itself Two conditions of recursion: baseline condition (satisfied, no recursion) and recursive condition (satisfied, baseline recursion) Recursion is similar to loop: it can basically replace each other Loop is easier to write and harder to read. Recursion is difficult to write, but easy to read

The above is the python recursion related knowledge summary of the details, more information about python recursion please pay attention to other related articles on this site!