脚本之家,脚本语言编程技术及教程分享平台!
分类导航

Python|VBS|Ruby|Lua|perl|VBA|Golang|PowerShell|Erlang|autoit|Dos|bat|

服务器之家 - 脚本之家 - Python - python 利用栈和队列模拟递归的过程

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

2021-02-26 00:27渔单渠 Python

这篇文章主要介绍了python 利用栈和队列模拟递归的过程,文中并通过两段代码给大家介绍了下递归和非递归的区别,需要的朋友可以参考下

一、递归

递归调用:一个函数,调用的自身,称为递归调用
递归函数:一个可以调用自身的函数称为递归函数

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

方法:

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

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

    输入一个大于等于1的数,求1到n的和!

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

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

?
1
2
3
4
5
6
# 递归
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的数全部递归完

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

二、递归遍历目录

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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的意思,有人也许现在就明白了。那个其实就是让我们方便观察,因为每次打印都是顶行写的,我们分不清他的目录结构,所以通过空格来调整。在函数内部写一个空格增加的表达式,可以使调用次数和空格数相关起来,递归的越深,证明目录的级越低,那么空格越多

三、模拟递归遍历目录(深度遍历)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 整体思路是没有变得,这里没有写到的也许是重复的,看下上面注释就好了
# 写了一半想起来应该回来写一下栈:栈就是一个容器,但它只有一个口,入栈出栈都从这一个口,而且这个栈很细,进去了就不能颠倒位置了,所以,每入栈一个元素他在最外面时候可以出来,否则得等前面的走完了它才可以出来
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)

 四、队列模拟递归遍历目录(广度遍历)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 这回记住了,先说一下队列,队是一个两端开口的模型,一头进一头出,当然还有双向队列,循环等等,我们就简单用一下最基本的队列
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) 
# 大家想一下,栈是哪里进哪里出,也就是,刚进去的元素,接下来的一次循环又出来了,那便是一条路走到头,是深度遍历;那么现在一头进另一头出是什么意思呢,就是即便判断了这个是一个目录,但我现在不执行你,我要把你前面这些都查一遍,找完是目录的都添加在后面,之后再遍历你们这些,就是把一层的内容找完再找下一层,被称为广度优先遍历。

总结

以上所述是小编给大家介绍的python 利用栈和队列模拟递归的过程,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对服务器之家网站的支持!

原文链接:https://www.cnblogs.com/yudanqu/p/9103413.html

延伸 · 阅读

精彩推荐