python USES stacks and queues to simulate the recursive process

1. The recursion

Recursive call: A function that calls itself, called a recursive call
Recursive functions: A function that can call itself is called a recursive function

Anything that loops can do, recursion can do

Methods:

1. Write the critical conditions
2. Find the relationship between this one and the last one
3. Assuming that the current function is already available, call itself to calculate the result of the last time and then work out the result of this time

Here's a quick look at the difference between recursion and non-recursion in two pieces of code:

Enter a number greater than or equal to 1, and find the sum from 1 to n!

#  Ordinary functional method 
def hanshu(n):
 sum = 0
 #  Loop through each 1 A number. Add them to 1 Of a predefined number of variables until you're done adding them 
 for x in range(1, n+1):
  sum += x
 return sum

Now let's look at the recursion method:

#  recursive 
def digui(n):
 if n == 1:
  return 1 #  if n Is equal to the 1 Prove that you've recursed to the end, return 1 That's the critical condition above 
 else:
  return n + digui(n-1) #  When the critical condition is not met n Combined with the n-1 Recursion of phi, every time n I'm going to add it in, but I'm going to use the same recursive function that I have now, and I'm going to call the calculation again n-1 Until the end of the recursion, that is, it will start from n to 1 The recursion is complete 

In practice, recursion consumes 10 cents of ram, but there are some things that are easy to do and easy to understand. Next, I will introduce the use of recursion in 1 through 1 case.

2. Recursively traverse the directory

The following content I explained the code to explain, if where to say is not clear, welcome to comment below.

import os #  Since we're walking through the directory, to find that directory and operate, os Modules contain universal operating system functions 
path = "" #  This is the path to the directory we're going to traverse, so we need to write it in 
#  Since it's a recursive function, there must be a function, and it will be called inside the function again 
def getAllDir(path, sp = ''): #  Pass in path and sp ", I said finally 1 You'll see 
 #  Gets all the files in the current directory 
 filesList = os.listdir(path) # os.listdir() is os Under the module of 1 Method, which is equivalent to Linux In the ls , to view all the files 
 sp += " " #  Here, too 1 Under the 
 #  Deal with each 1 A file 
 for fileName in filesList: #  Go through all the files in the directory you just found 
  #  Determine if it is a directory (to use an absolute path) 
  fileAbsPath = os.path.join(path,fileName) # join is os Two paths are spliced together under the module 1 The meaning of rise, number one 2 The parameters cannot have slashes. Because we have to judge 1 The next file is 1 A regular file or 1 Ten directories, so you have to sort out its absolute path first 
  if os.path.isdir(fileAbsPath): # isdir Is to determine whether it is a directory, is to return True
   print(sp + " Directory: ", fileName) #  Print the current file, which is a directory 
   getAllDir(fileAbsPath,sp = " ") #  This is where the recursion starts, because we're going to find the entire directory, so we need to keep looking down while this file is still a directory 
  else:
   print(sp + " General file: ", fileName) #  If it's just an ordinary file, then there's no other file in it, so you can just print it 
getAllDir(path) #  Here's the call function to start the traversal 
#  And finally Let me say 1 The one that I started with sp , it is space Some of you may know it now. That's just to make it easy for us to see, because every time we print it, it's the top line, and we can't tell its directory structure apart, so we use Spaces to adjust it. Write it inside the function 1 An expression that increases the number of Spaces can be used to correlate the number of calls with the number of Spaces. The deeper the recursion, the lower the level of the directory, the more Spaces 

3. Stack simulation recursive traversal directory (depth traversal)

#  The whole idea is that it's not getting, what's not written here is probably repetitive, just look at the comments above 
#  To write a 1 I think I should come back 1 Lower stack: A stack is 1 It's a container, but it's only a container 1 One entry, one entry and one exit all from here 1 A mouth, and this stack is very thin, into the position can not be reversed, so, every push stack 1 He can come out at the most outside of the element, otherwise, he has to wait for the front to walk it can come out 
import os
def getAllDirDFS(path):
 stack = [] #  So here's a stack simulation, so let's create it 1 The list ACTS as a stack 
 stack.append(path) #  First, push the path into the stack 
 #  Process the stack, and end the loop when the stack is empty (empty means there are no normal files and directories left on the stack, because we are doing every operation 1 One wants to take that out.) 
 while len(stack) != 0:
  #  Pulling data from the stack 
  dirPath = stack.pop() # pop The function is deleted last 1 The elements, and the elements 1 The return value, the element that was removed, we receive 1 Next, and so on with 
  #  All files in the directory 
  filesList = os.listdir(dirPath) #  This and the top 1 sample 
  #  Deal with each 1 If it's a normal file, print it out. If it's a directory, push the directory address onto the stack 
  for fileName in filesList:
   # print(dirPath)
   fileAbsPath = os.path.join(dirPath,fileName)
   # print(fileAbsPath)
   if os.path.isdir(fileAbsPath):
    #  Is the directory on the stack 
    print(" Directory: " + fileName)
    stack.append(fileAbsPath) #  When you push a directory, it's on the outside, on the bottom 1 Is this the same stack element that you want to take out in the next loop? If it is, you will have to look inside it and wait until you have found it before you continue to look for the files that are next to it. That is to say seize 1 A string tries to find its way down, finds its head and comes back, which is depth-first traversal 
   else:
    #  Print plain file 
    print(" General: " + fileName)
getAllDirDFS(path)

4. Queue simulation recursive traversal directory (breadth traversal)

#  This time remember, speak first 1 Down line, down line 1 A model with two open ends, 1 Head into the 1 Head out, and of course two-way queues, loops and so on, we'll just use that 1 Let's go to the most basic queue 
import collections #  Queue in python ", so we call it directly 1 Below, don't think this is difficult, he is also just a type is queue , the actual idea is 1 Yes, join the team append Because this is on the right, which is the rear entry, and 1 So that's going to be the edge popleft On the left, it's not very popular, it's just changed 1 The opening from the bottom 
def getAllDirBFS(path):
 queue = collections.deque() #  create 1 A queue, just remember that the latter usage is the difference I mentioned above 
 queue.append(path)
 while len(queue) != 0:
  dirPath = queue.popleft() #  It's just different here, because the queue simulation is another 1 Set out team 
  filesList = os.listdir(dirPath)
  for fileName in filesList:
   fileAbsPath = os.path.join(dirPath,fileName)
   if os.path.isdir(fileAbsPath):
    print(' Directory: ' + fileName)
    queue.append(fileAbsPath)
   else:
    print(' File: ' + fileName)
getAllDirBFS(path)  
#  They want to 1 Down, where does the stack go in and out, that is, what just went in, what's next 1 The cycle comes out again, and that is 1 The end of the road, is the depth of traversal; So now 1 Head into the other 1 What does it mean to be a prima facie, even if you know what this is 1 A directory, but I'm not executing you right now, I'm going to check these out before you 1 Go through, find out is the directory are added to the back, and then go through these of you, is to put 1 Look for the content of the layer after you find it 1 Layers, called breadth first traversal. 

conclusion