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