It’s always nice to hear about recursion. Why? Because I’m not familiar with recursion, I’m going to write this article to remember what recursion really is.

But before you worry, let’s look at a problem: find the factorial of 10. .

The factorial of x is just multiplying from 1 to x. So 10 factorial is 1 times 2 times 3 times 4 times 5 times 6 times 7 times 8 times 9 times 10

1. Factorial in a non-recursive way

How do we solve this problem if we haven’t touched recursion?

Print (1*2*3*4*5*6*7*8*9*10) and print(3628800).

This is obviously not what we want, so try a for loop.

Def factorial(n): "" result = n for I in range(1, n): result *= i return result if __name__ == '__main__': print(factorial(10))Copy the code

Two, recursive way to find the factorial

1. What is recursion?

I’m sure you’ve all heard the story:

Once upon a time, there was a mountain with a temple in it. In the temple, an old monk was telling a story. What was he telling? Once upon a time, there was a mountain with a temple in it. In the temple, an old monk was telling a story. What was he telling? Once upon a time, there was a mountain with a temple in it. In the temple, an old monk was telling a story. What was he telling? .Copy the code

In fact, this kind of recursion, in plain English, refers to oneself. So, recursion in a function could look like this:

def factorial():
    factorial() 

if __name__ == '__main__':
    factorial()
Copy the code

Call factorial in the same function as the story above, and you can keep recursing until the old monk gets tired and the computer runs out of memory and crashes.

But, the important thing is, recursion is just one way to solve a problem, like the factorial above, that I did with a for loop.

2. Solve factorials recursively

If you want to recursively solve the factorial problem above, you can understand the whole idea of recursion below.

The whole idea of recursion is to take a big problem and break it down into smaller problems until you can’t break it down any more, and then you solve it. So, the recursive function must satisfy two conditions:

  • Baseline condition: the problem can be decomposed into the smallest problem. When the baseline condition is met, recursion is no longer performed
  • Recursion condition: Continue to decompose the problem and use this idea to try to solve the factorial problem recursively.
10! = 10 * 9! The factorial of # 10 can be viewed as 10 times 9 factorial of 9 factorial. = 8 * 8! The factorial of # 9 can be viewed as 9 times 8 factorial of 8 factorial. = 8 * 7! . 2! * 1 = 2! 1! = 1Copy the code

As you can see, when you finally get to 1 you can’t do any more decomposition, so 1 is the baseline condition.

Def factorial(n): if n == 1: Return n * factorial(n-1) if __name__ == '__main__': print(factorial(10))Copy the code

Third, summary

  • Recursion: Just a way of solving a problem, not necessarily
  • Recursive functions: the function calls itself
  • 2 conditions for recursion: baseline condition (satisfied, no recursion), recursion condition (satisfied, baseline recursion)
  • Recursion is like a loop: it’s basically interchangeable
  • Loops are easy to write and hard to read. Recursion is hard to write, but easy to read