# The idea and implementation of recursion in data structure (Python)

### recursive

#### 1. recursive

​ 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
``````

Cyclic process

​ 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 ：

Using recursion

``````def listSum(numList):
if len(numList) == 1:
return numList[0]
else:
return numList[0] + 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([5]) That's the least boy problem ）：

Recursive principle

​ From the above example, we can sum up three principles about recursion ：

• Recursive algorithms must have basic conditions ;
• The recursive algorithm must change its state and move closer to the basic situation ;
• Recursive algorithms must call themselves recursively .

https://cdmana.com/2021/10/20211002150018479f.html

Scroll to Top