这都不会，还学什么Python（利用栈和队列模拟递归）这都不会，还学什么Python？利

下面从一个尽量贴近一个初学者的角度，给大家细致入微的了解一下Python中的递归。
一，递归

递归调用：一个函数，调用的自身，称为递归调用
递归函数：一个可以调用自身的函数称为递归函数

凡是循环能干的事，递归都能干
方法：
1``、写出临界条件
2``、找这一次和上一次的关系
【这都不会，还学什么Python（利用栈和队列模拟递归）】3``、假设当前函数已经能用，调用自身计算上一次的结果再求出本次的结果
下面我们通过两段代码简单看一下递归和非递归的区别：
输入一个大于等于1的数，求1到ň的和！

1 # 普通函数方法 2 3 def hanshu(n): 4sum = 0 5# 循环遍历每一个数字，将他们加到一个事先定义好的变量上，直到加完 6for x in range(1, n+1): 7sum += x 8return sum

文章图片
Python资料学习群519970686 下面看一下通过递归的方法：

1 # 递归 2 3 def digui(n): 4if n == 1: 5return 1 # 如果n等于1证明已经递归到最后，返回1，这就是上述的临界条件 6else: 7return n + digui(n-1) # 当没有达到临界条件时，用n加上对n-1的递归，每次都把n加进去，但是后面依然是使用当下这个递归函数，会再次调用计算n-1，直到递归结束，也就是将从n到1的数全部递归完

文章图片
在实际应用中，递归是十分消耗内存的，但是有些事情他很容易去做，很容易理解。下面，就通过一个案例介绍一下递归的用法。
二，递归遍历目录下面的内容我就通过解释代码来讲解了，如果哪里讲的不清楚，欢迎大家下方评论提意见。

1 import os # 由于我们遍历目录，所以要找到那个目录并操作，os模块包含普遍的操作系统功能 2 3 path = "" # 这是我们要遍历的目录的路径，需要自己写进去 4 5 # 既然是递归函数，那么肯定要有个函数，而且这个函数还将在函数内部再次被调用 6 def getAllDir(path, sp = ''): # 参数中传入路径和sp，这个我最后说一句你就明白了 7# 得到当前目录下的所有文件 8filesList = os.listdir(path) # os.listdir()是os模块下的一个方法，相当于Linux中的ls，查看所有文件 9 10sp += "" # 这个也先放一下 11# 处理每一个文件 12for fileName in filesList: # 遍历刚才找到的目录下的所有文件 13# 判断是否是目录（要用绝对路径） 14fileAbsPath = os.path.join(path,fileName) # join是os模块下将两个路径拼接在一起的意思，第二个参数不能有斜杠。因为我们要判断一下这个文件是一个普通文件还是一个目录，所有要先把他的绝对路径整理出来 15if os.path.isdir(fileAbsPath): # isdir是判断是否为目录，是则返回True 16print(sp + "目录：", fileName) # 打印当前这个文件，他是个目录 17getAllDir(fileAbsPath,sp = "") # 这里就开始递归了，因为我们要找到整个目录里的东西，所以当这个文件还是个目录的时候我们需要继续向下找 18else: 19print(sp + "普通文件：", fileName) # 如果仅仅是个普通文件，那么他里面也就没有其他文件了，就可以直接打印他了 20 21 22 getAllDir(path) # 这里是调用函数，让遍历开始 23 24 # 最后我来说一下开始写的那个sp，是space的意思，有人也许现在就明白了。那个其实就是让我们方便观察，因为每次打印都是顶行写的，我们分不清他的目录结构，所以通过空格来调整。在函数内部写一个空格增加的表达式，可以使调用次数和空格数相关起来，递归的越深，证明目录的级越低，那么空格越多

文章图片
三，栈模拟递归遍历目录（深度遍历）

1 # 整体思路是没有变得，这里没有写到的也许是重复的，看下上面注释就好了 2 # 写了一半想起来应该回来写一下栈：栈就是一个容器，但它只有一个口，入栈出栈都从这一个口，而且这个栈很细，进去了就不能颠倒位置了，所以，每入栈一个元素他在最外面时候可以出来，否则得等前面的走完了它才可以出来 3 import os 4 5 def getAllDirDFS(path): 6stack = [] # 这里是用栈来模拟，我们先创建一个列表当做栈 7stack.append(path) # 首先，先向栈里压入路径 8 9# 处理栈，当栈为空时结束循环（栈为空就说明栈里没有普通文件和目录了，因为我们是每操作一个要把那个取出来） 10while len(stack) != 0: 11# 从栈中取出数据 12dirPath = stack.pop() # pop函数是删除最后一个元素，同时还有一个返回值，就是去除的那个元素，我们再接收一下等等用 13# 目录下所有文件 14filesList = os.listdir(dirPath) # 这个和上面一样 15 16# 处理每一个文件，如果是普通文件则打印出来，如果是目录则将该目录地址压栈 17for fileName in filesList: 18# print(dirPath) 19fileAbsPath = os.path.join(dirPath,fileName) 20# print(fileAbsPath) 21if os.path.isdir(fileAbsPath): 22# 是目录就压栈 23print("目录：" + fileName) 24stack.append(fileAbsPath) # 当是目录时入栈，它这时就在最外面，下一次循环时候要取出栈的元素是不是还是这个啊，既然是它的话就还有找他内部的东西，等把他找完了才继续找和他并列的那些文件。就是说抓住一根绳子使劲往下找，找到头没有了才返回来，这就是深度优先遍历 25else: 26# 打印普通文件 27print("普通：" + fileName) 28 29 getAllDirDFS(path)

文章图片
四，队列模拟递归遍历目录（广度遍历）

1 # 这回记住了，先说一下队列，队是一个两端开口的模型，一头进一头出，当然还有双向队列，循环等等，我们就简单用一下最基本的队列 2 3 import collections # 队列在python的包里有，所以我们直接调用一下，不用以为这个很难，他也只不过是类型是queue，实际的思想是一样的，入队append，因为这个是在右侧，也就是后方入队，另一边出的话就是popleft，左侧出，是不是很通俗，只是改了一下出来的口 4 def getAllDirBFS(path): 5queue = collections.deque() # 创建一个队列，只要记得后面用法就是上面我说的那个不同就可以了 6queue.append(path) 7 8while len(queue) != 0: 9dirPath = queue.popleft() # 仅仅这里不同，因为队列模拟是另一端出队 10filesList = os.listdir(dirPath) 11for fileName in filesList: 12fileAbsPath = os.path.join(dirPath,fileName) 13if os.path.isdir(fileAbsPath): 14print('目录：' + fileName) 15queue.append(fileAbsPath) 16else: 17print('文件：' + fileName) 18 19 getAllDirBFS(path) 20 21 # 大家想一下，栈是哪里进哪里出，也就是，刚进去的元素，接下来的一次循环又出来了，那便是一条路走到头，是深度遍历；那么现在一头进另一头出是什么意思呢，就是即便判断了这个是一个目录，但我现在不执行你，我要把你前面这些都查一遍，找完是目录的都添加在后面，之后再遍历你们这些，就是把一层的内容找完再找下一层，被称为广度优先遍历。