## I've heard it n times, but I'm not impressed. After reading this, you'll understand

Bite the apple and cry 2021-02-22 15:15:12
ve heard times impressed. impressed

I always feel tall when I hear recursion , Why? ？ Because I'm not familiar with it , So let's write today to remember what recursion is .

But don't worry , Let's look at a problem ： seek 10 The factorial （10！）.

seek x The factorial , In fact, from 1 Start to multiply one by one to x. that 10 The factorial of is `1*2*3*4*5*6*7*8*9*10`

### One 、 Factorial in a non recursive way

If , We don't touch recursion , How to solve such a problem ？

The simplest and rudest way direct `print(1*2*3*4*5*6*7*8*9*10)` The result is OK , The result is `3628800`.

But this is obviously not what we want , Then you can try for In a circular way .

``````def factorial(n):
"""
n It's the number of the required factorial
"""
result = n
for i in range(1, n):
result *= i
return result
if __name__ == '__main__':
print(factorial(10))
``````

### Two 、 Factorial recursion

#### 1. What is recursion ？

I believe everyone must have heard such a story ：

`````` Once upon a time there was a mountain , There are temples in the mountains , There is an old monk in the temple telling a story , What are you talking about ？
Once upon a time there was a mountain , There are temples in the mountains , There is an old monk in the temple telling a story , What are you talking about ？
Once upon a time there was a mountain , There are temples in the mountains , There is an old monk in the temple telling a story , What are you talking about ？
...
``````

In fact, this is recursion , To put it bluntly , It's about quoting yourself .
that , Recursion is used in functions , It could look like this ：

``````def factorial():
factorial()
if __name__ == '__main__':
factorial()
``````

Calling function `factorial` When Continue calling... In the function `factorial`, Just like the story above , You can recurse endlessly ,
Until the old monk who told the story fainted , As well as the computer's memory overflow downtime .

however , One important point , Recursion is just a way to solve problems , Like factorial above , I use for It's the same as the loop .

#### 2. Recursively solve factorial

If you want to solve the factorial problem above with recursion , You can learn more about the whole idea of recursion .

The whole idea of recursion is , Decompose a big problem into small ones , Until there's no way to break it down , therefore , Then solve the problem .
that , A recursive function has to satisfy 2 Conditions ：

• Baseline condition ： The problem can be decomposed into the smallest problem , When the baseline conditions are met , Recursion is no longer going on
• Recursive conditions ： Continue to decompose the problem
We can use this idea to try to solve the factorial problem recursively .
``````10! = 10 * 9! # 10 The factorial of is actually 10 * 9 The factorial
9! = 9 * 8! # 9 The factorial of is 9 * 8 The factorial
8! = 8 * 7!
...
2! = 2 * 1!
1! = 1
``````

You can see , Finally, it's broken down to 1 You can't continue to decompose when you're in trouble , that 1 That's the baseline condition .

``````def factorial(n):
# Baseline condition , When satisfied , No more recursion
if n == 1:
return 1
# Recursive conditions , When n It's not equal to 1 when , Continue to recursive
return n * factorial(n - 1)
if __name__ == '__main__':
print(factorial(10))
``````

### 3、 ... and 、 summary

• recursive ： It's just a way to solve problems , It doesn't have to be
• Recursive functions ： The function calls itself
• Recursive 2 Conditions ： Baseline condition （ If satisfied, there is no recursion ）、 Recursive conditions （ If satisfied, the baseline recursion ）
• Recursion is like a loop ： Basically, they can replace each other
• It's easier to write loops , It's hard to read . Recursion is hard to write , But it's easy to read

https://pythonmana.com/2021/02/20210221221433715S.html