python 利用栈和队列模拟递归的过程

一、递归

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

　　凡是循环能干的事，递归都能干

方法：

1、写出临界条件
2、找这一次和上一次的关系
3、假设当前函数已经能用，调用自身计算上一次的结果再求出本次的结果

　　下面我们通过两段代码简单看一下递归和非递归的区别：

　　　　输入一个大于等于1的数，求1到n的和！

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

　　下面看一下通过递归的方法：

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

　　在实际应用中，递归是十分消耗内存的，但是有些事情他很容易去做，很容易理解。下面，就通过一个案例介绍一下递归的用法。

二、递归遍历目录

　　下面的内容我就通过解释代码来讲解了，如果哪里讲的不清楚，欢迎大家下方评论提意见。

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