Detailed Explanation of Recursion and Recursive Traversal Directory in Python

Directory recursion Recursive summation
Recursive processing of nonlinear loops
Spending recursion
Recursive considerations
Implement the Tree command Summarize

Recursion

The concept of recursion: If a function contains a call to itself, then it is recursive

Scenario used: If you find that what you are going to do is what you are doing now, use recursion

Recursion is similar to loop; When writing or reading recursion, the first thing we pay attention to is the termination conditions of recursion

Recursive summation

Before we get to recursion, let's do this question first: If we want to sum a list of numbers (or other sequences), what else can we do except use the built-in sum function?

while cycle

L = [1,2,3,4,5]
mysum = 0 # Save variables of sum 
while L: # Make the list the most circular condition 
	mysum += L[0] # Put the list at each time 1 The value of the position is added to the sum 
	L = L[1 : ] # Remove the list number 1 Elements 

for cycle

L = [1,2,3,4,5]
mysum = 0
for var in L:
	mysum += var

Recursive summation

def mysum(L):
    if not L:
        print ('L is empty')
        return 0
    else:
      	return L[0]+mysum(L[1:])
#  In the return value, we return the 1 A call to a function, and the parameter passed is to remove the first of the current list 1 A new list of elements 

Recursive processing of nonlinear loops

Recursion can also deal with some nonlinear loops, but ordinary loops cannot be dealt with; For example, a list sums it:

L = [1,[2,[3,4],5],6,[7,8]]

Because this list is not a linear iteration and contains complex nesting of elements, ordinary loop statements will be very difficult to control

L = [1,[2,[3,4],5],6,[7,8]]
sum = 0
def mysum(L):
    global sum
    for var in L:
    	if not isinstance(var,list):   
            # If the element is not of list type; Otherwise, 1 Determined values 
            sum += var
        else:
         	mysum(var)
    return

Spending recursion

Thinking: If you have 10000 yuan, spend 1.5 yuan every day, and give up the dime directly, how many days can this money spend?

Recursive resolution:

def cost(money,day=0):
    if money > 0:
        money = money // 2 # Every flower 1 Half 
        day += 1 # Days spent +1
        cost(money,day) # Turn on spending recursion 
    else:
        print('1 Total flowers %d Days ' % day)
        return # What must be 1 Termination conditions 

Recursive considerations

In Python, the maximum number of recursions is almost 998, and a recursion without termination conditions will cause an error (similar to an infinite loop)

This is because every time a recursive function is executed, a new copy of the function will be generated in memory, and the memory consumption of recursion is larger than that of ordinary loop

>>> def func():
...     return func()
...
>>> func()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in func
  File "<stdin>", line 2, in func
  File "<stdin>", line 2, in func
  [Previous line repeated 995 more times]
RecursionError: maximum recursion depth exceeded
# Here we are 995 After the second recursion, it reaches the online line, thus reporting an error 

We can also manually interfere with the upper limit of recursion, but this is risky and should be considered in combination with the computer's own memory

>>> import sys
>>> sys.setrecursionlimit(num)
# num Maximum number of recursive upper limits for control modifications 

Implement the Tree command

The core idea is that the depth and breadth of the directory structure are complicated, and it is a very difficult thing to make judgments through simple circulation

And recursion is just suitable for such a nonlinear loop problem, of course, there are also some disadvantages, when the directory structure is more and more complex, then the execution efficiency of the program will become worse and worse

import os

def getdir(path, level=0):
    if path == '':
      	path = os.getcwd()  #  Get the current working directory 
    level += 4
    num = level // 4
    abs_path = os.path.abspath(path)
    for name in os.listdir(path):  #  Returns the 1 List 
        format_str = ''
        if os.path.isfile(os.path.join(abs_path, name)):
            for var in range(num):  # range The function is used to control the number of cycles 
              	format_str += '_' * 4 + ' Attain '
            format_str = format_str[0:-1]
            format_str += name
            mystr = format_str.replace('_', ' ', level-4)  #  Replace level-4 A _
    else:
        for var in range(num): # range The function is used to control the number of cycles 
            format_str += '_' * 4 + ' Attain ' #  Output style construction 
        format_str += name
        mystr = format_str.replace('_',' ',level-4) #  Replace level-4 A _
    print(mystr) #  Output format string 
    name = os.path.join(abs_path,name)
    if os.path.isdir(name): #  Absolute path , Determine whether it is a folder 
	    getdir(name,level)
path = input(' Please enter the directory you want to traverse: ')
getdir(path)

Summarize