递归Recursion-蒲公英云

递归Recursion

Bertha 。 2023-10-09 10:32 71阅读 0赞

递归

递归都可以用循环实现,反之不一定

递归应用 : DFS 深度优先搜索、前中后序二叉树遍历等等

递归需要满足的三个条件

1> 一个问题的解可以分解为几个子问题的解

2> 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样

3> 存在递归终止条件

如何编写递归代码

写出递推公式，找到终止条件

编写递归代码的关键是，只要遇到递归，把它抽象成一个递推公式，不用想一层层的调用关系不要试图用人脑去分解递归的每个步骤

递归缺点

堆栈溢出，重复计算，函数调用耗时多，空间复杂度高

递归调试

1>打印日志发现递归值

2> 结合条件断点进行调试

# !< eg: def count(n): for i in range(n): print(i) def count_re(n): if n > 1: count_re(n-1) print(n-1) count_re(10)
def fib(n): if n == 1: return 1 if n == 2: return 1 return fib(n - 1) + fib(n - 2) print(fib(3))
def add(self, v): if self.next is not None: return self.next.add(v) self.v = Node(v)