directory

 

recursive

Write recursively:

Analog stack structure

The queue

Recursively traverse the directory

Stack simulates recursive traversal of directories (deep traversal)

Queue simulation recursion (breadth traversal)

recursive

Recursive call: A function that calls itself is called a recursive call. A function that calls itself is called a recursive function

Recursion can do anything a loop can do

 

Write recursively:

  1. Write the critical condition
  2. Find the relationship between this time and the last time
  3. Assuming that the current function is available, call itself to calculate the last result and then compute the result

Enter n to find 1+2+3+…… The value of + n

Method 1:

a = int(input("Please enter a number:"))
b = 0
def fun(a,b) :
    if a>0:
        b += a
        a = a-1
        fun(a,b)
    else:
        print(b)

fun(a,b)
Copy the code

Method 2:

That’s fun(1)+2 = fun(2)

fun(2) + 3 = fun(3)

fun(3) + 4 = fun(4)

fun(4) + 5 = fun(5)

a = int(input("Please enter a number:"))
def fun(a) :
    if(a==1) :return a
    return a + fun(a-1)

print(fun(a))
Copy the code

 

Analog stack structure

After the advanced

# Simulate stack structure
stack = []

# push (add data to the stack)
stack.append('a')
stack.append('b')
stack.append('c')
print(stack)

# unstack (fetch data from the stack)
res = stack.pop()
print(res)
print(stack)
res = stack.pop()
print(res)
print(stack)
Copy the code

 

The queue

First in first out

import collections

Create a queue
queue = collections.deque()
print(queue)

# queue (data stored in queue)
queue.append('a')
queue.append('b')
queue.append('c')
print(queue)

# queue (fetch data from queue)
res = queue.popleft()
print(res)
print(queue)
res = queue.popleft()
print(res)
print(queue)
Copy the code

Recursively traverse the directory

import os

Get all files in the current directory recursively
def get(path) :
    Get a list of files in the current directory
    file = os.listdir(path)
    # Process each file
    for name in file:
        To check whether a file is a directory, use an absolute path
        if os.path.isdir(os.path.join(path,name)):
            print("Contents:",name)
            get(os.path.join(path,name))
        else:
            print("Ordinary documents:",name)
get(r"F:\pycharm")
Copy the code

import os

Get all files in the current directory recursively
def get(path,sp) :
    Get a list of files in the current directory
    file = os.listdir(path)
    # Process each file
    sp += ""
    for name in file:
        To check whether a file is a directory, use an absolute path
        if os.path.isdir(os.path.join(path,name)):
            print(sp+"Contents:",name)
            get(os.path.join(path,name),sp)
        else:
            print(sp+"Ordinary documents:",name)
get(r"F:\pycharm"."")
Copy the code

 

Stack simulates recursive traversal of directories (deep traversal)

Depth-first Traversal

Suppose that the initial state of a given graph G is that all vertices are not visited. If any vertex V in G is selected as the initial starting point (source point), then depth-first traversal can be defined as follows: first, the starting point V is visited and marked as visited; And then search for each of v’s adjacent points, W, starting from v. If w has not been visited, the depth-first traversal will be continued with W as the new starting point until all vertices in the graph that have path communication with the source point V (also known as vertices reachable from the source point) have been visited. If there are still unvisited vertices in the graph, another unvisited vertex is selected as a new source point and the above process is repeated until all vertices in the graph are accessed.

Depth-first traversal of a graph is similar to pre-order traversal of a tree. The characteristic of the search method is to search the depth direction as far as possible. This Search method is called depth-first Search. Accordingly, traversing a graph in this way is naturally called depth-first traversal of the graph.

Let x be the currently accessed vertex and, after marking x for access, select an undetected edge (x, y) from x. If it is found that vertex Y has been visited, it selects another undetected edge starting from x, otherwise the edge (x, y) reaches the unvisited Y, accesses y and marks it as visited; Then the search starts from y, and does not go back to vertex X until all paths from y have been searched, that is, all vertices reachable from y have been visited, and another undetected edge from x has been selected. This process continues until all edges starting from X have been examined. At this point, if x is not the source, the vertices accessed before x are retraced; Otherwise, all vertices in the graph that have path connection with the source point (that is, all vertices reachable from the source point) have been accessed. If graph G is a connected graph, the traversal process ends; otherwise, a vertex that has not been accessed is selected as a new vertex to continue traversal.

import os
def get(path) :
    stack = []
    stack.append(path)
    # process the stack and end the loop when the stack is empty
    while len(stack) ! =0:
        # Fetch data from the stack
        dirpath = stack.pop()
        All files in the directory
        dirlist = os.listdir(dirpath)
        #print(dirlist)
        Print each file, if it is a normal file, if it is a directory, then push the directory address
        for filename in dirlist:
            filepath = os.path.join(dirpath,filename)
            if os.path.isdir(filepath):
                # is directory, push
                print("Contents:",filename)
                stack.append(filepath)
            else:
                # Not a directory, print
                print("Ordinary documents:",filename)

get(r"F:\pycharm")
Copy the code

 

Queue simulation recursion (breadth traversal)

import os
import collections
def get(path) :
    queue = collections.deque()
    # into the team
    queue.append(path)

    while len(queue) ! =0:
        # Exit data
        dirpath = queue.popleft()

        Find all the files
        filelist = os.listdir(dirpath)
        for filename in filelist:
            # absolute path
            filepath = os.path.join(dirpath, filename)
            if os.path.isdir(filepath):
                # is directory, push
                print("Contents:", filename)
                queue.append(filepath)
            else:
                # Not a directory, print
                print("Ordinary documents:", filename)

get(r"F:\pycharm")
Copy the code

 

 

Learn together and make progress together. If there are any mistakes, please comment