Recursion is a common idea in data structures and when we write code , Through recursion, the problem can be continuously divided into smaller subproblems , Until the subproblem can be solved in an ordinary way , Usually , Recursion uses a function that keeps calling itself .
Many people compare loops with recursion , Let's take a look at the difference between recursion and loop through a small case .
for instance ： Calculation [1,2,3,4,5] The sum of .
Using a loop
count = 0 numList = [1, 2, 3, 4, 5] for i in numList: count += i count # Output 15
When using cycles , Each time, one element is extracted from the list and added to the sum of the previous elements , When the loop ends, all the elements are added in turn . The specific internal process is shown in the figure below ：
def listSum(numList): if len(numList) == 1: return numList else: return numList + listSum(numList[1:]) numList = [1, 2, 3, 4, 5] listSum(numList) # Output 15
A recursive process
It's not hard to find out , Recursion is implemented by a function body , Inside the function, the function itself is called , In fact, this is also the essence of recursion （ Call yourself repeatedly ）, When the conditions in the function are not enough to call itself , It's the one we're looking for “ The smallest question ”（ Problems that can be solved in the most common way ）, Let's solve this first “ The smallest question ” Then go to solve a bigger problem , By analogy, we can find a formula to solve the problem , The biggest problem of calling this formula repeatedly is easy to solve . Recursive internal flow chart （Sum() That's the least boy problem ）：
From the above example, we can sum up three principles about recursion ：