为什么树的深度优先遍历可以写成递归模式,而宽度优先遍历不能?

今天在讨论python题目时,被某人今天问了一个问题:为什么树的深度优先遍历可以写成递归模式,而宽度优先遍历不能?。仔细讲解以后,还要我作个笔记,并给出以下提示:
1. 递归与函数的关系
2. 叙述系统如何为函数分配内存

3. 叙述系统为函数分配内存的数据结构的是什么

4. 叙述这个数据结构与一个函数是否能够写成递归的关系

5. 扩展:叙述一个通用的办法,这个办法可以把所有递归的算法写成非递归算法

笔记如下:
递归是在满足一定条件下,同一函数的逐级调用。
系统采用栈保存函数的首地址和参数。栈具有“先进后出”特点,刚好可以实现递归函数的调用关系。深度优先遍历是可以用栈表示的过程,而宽度优先遍历不可以,因此,可以采用递归实现,而宽度优先遍历不能。
由于系统为栈分配的大小是一定,比如2M,且栈是由高地址向低地址分配的,因此递归方法要预防出现“栈溢出”的异常。
通常,一个递归算法可以通过采用栈保存数据改写成一个非递归算法。

发表评论

邮箱地址不会被公开。 必填项已用*标注