下面从一个尽量贴近一个初学者的角度, 给大家细致入微的了解一下 Python 中的递归.
一, 递归
递归调用: 一个函数, 调用的自身, 称为递归调用
递归函数: 一个可以调用自身的函数称为递归函数
凡是循环能干的事, 递归都能干
方法:
1``, 写出临界条件
2``, 找这一次和上一次的关系
3``, 假设当前函数已经能用, 调用自身计算上一次的结果再求出本次的结果
下面我们通过两段代码简单看一下递归和非递归的区别:
输入一个大于等于 1 的数, 求 1 到ň的和!
- # 普通函数方法
- def hanshu(n):
- sum = 0
- # 循环遍历每一个数字, 将他们加到一个事先定义好的变量上, 直到加完
- for x in range(1, n+1):
- sum += x
- return sum
Python 资料学习群 519970686
下面看一下通过递归的方法:
- # 递归
- 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 的意思, 有人也许现在就明白了. 那个其实就是让我们方便观察, 因为每次打印都是顶行写的, 我们分不清他的目录结构, 所以通过空格来调整. 在函数内部写一个空格增加的表达式, 可以使调用次数和空格数相关起来, 递归的越深, 证明目录的级越低, 那么空格越多
三, 栈模拟递归遍历目录 (深度遍历)
- # 整体思路是没有变得, 这里没有写到的也许是重复的, 看下上面注释就好了
- # 写了一半想起来应该回来写一下栈: 栈就是一个容器, 但它只有一个口, 入栈出栈都从这一个口, 而且这个栈很细, 进去了就不能颠倒位置了, 所以, 每入栈一个元素他在最外面时候可以出来, 否则得等前面的走完了它才可以出来
- import os
- def getAllDirDFS(path):
- stack = [] # 这里是用栈来模拟, 我们先创建一个列表当做栈
- stack.append(path) # 首先, 先向栈里压入路径
- # 处理栈, 当栈为空时结束循环 (栈为空就说明栈里没有普通文件和目录了, 因为我们是每操作一个要把那个取出来)
- while len(stack) != 0:
- # 从栈中取出数据
- dirPath = stack.pop() # pop 函数是删除最后一个元素, 同时还有一个返回值, 就是去除的那个元素, 我们再接收一下等等用
- # 目录下所有文件
- filesList = os.listdir(dirPath) # 这个和上面一样
- # 处理每一个文件, 如果是普通文件则打印出来, 如果是目录则将该目录地址压栈
- for fileName in filesList:
- # print(dirPath)
- fileAbsPath = os.path.join(dirPath,fileName)
- # print(fileAbsPath)
- if os.path.isdir(fileAbsPath):
- # 是目录就压栈
- print("目录:" + fileName)
- stack.append(fileAbsPath) # 当是目录时入栈, 它这时就在最外面, 下一次循环时候要取出栈的元素是不是还是这个啊, 既然是它的话就还有找他内部的东西, 等把他找完了才继续找和他并列的那些文件. 就是说抓住一根绳子使劲往下找, 找到头没有了才返回来, 这就是深度优先遍历
- else:
- # 打印普通文件
- print("普通:" + fileName)
- getAllDirDFS(path)
四, 队列模拟递归遍历目录 (广度遍历)
- # 这回记住了, 先说一下队列, 队是一个两端开口的模型, 一头进一头出, 当然还有双向队列, 循环等等, 我们就简单用一下最基本的队列
- import collections # 队列在 python 的包里有, 所以我们直接调用一下, 不用以为这个很难, 他也只不过是类型是 queue, 实际的思想是一样的, 入队 append, 因为这个是在右侧, 也就是后方入队, 另一边出的话就是 popleft, 左侧出, 是不是很通俗, 只是改了一下出来的口
- def getAllDirBFS(path):
- queue = collections.deque() # 创建一个队列, 只要记得后面用法就是上面我说的那个不同就可以了
- queue.append(path)
- while len(queue) != 0:
- dirPath = queue.popleft() # 仅仅这里不同, 因为队列模拟是另一端出队
- filesList = os.listdir(dirPath)
- for fileName in filesList:
- fileAbsPath = os.path.join(dirPath,fileName)
- if os.path.isdir(fileAbsPath):
- print('目录:' + fileName)
- queue.append(fileAbsPath)
- else:
- print('文件:' + fileName)
- getAllDirBFS(path)
- # 大家想一下, 栈是哪里进哪里出, 也就是, 刚进去的元素, 接下来的一次循环又出来了, 那便是一条路走到头, 是深度遍历; 那么现在一头进另一头出是什么意思呢, 就是即便判断了这个是一个目录, 但我现在不执行你, 我要把你前面这些都查一遍, 找完是目录的都添加在后面, 之后再遍历你们这些, 就是把一层的内容找完再找下一层, 被称为广度优先遍历.
来源: http://www.jianshu.com/p/7f295b4474d9