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


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
# Output 

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 :

 Insert picture description here

Using recursion

def listSum(numList):
if len(numList) == 1:
return numList[0]
return numList[0] + listSum(numList[1:])
numList = [1, 2, 3, 4, 5]
# Output 

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

 Insert picture description here

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 .
Please bring the original link to reprint ,thank
Similar articles