如何将递归转成迭代
标签: # iteration # recursion # LeetCode # Python # 迭代 # 递归 # 算法

要理解递归,先得理解递归 发现问题 函数的递归调用是码农在日常工作中不可或缺的利器,在某些问题上,函数递归可以提供更为简洁的代码实现和更为直观的阅读理解,比如说我们很熟悉的树形结构的遍历。 然而,当函数调用的层数过多的时候,就可能导致著名的 Stack Overflow 错误,而栈空间一般是由编译器( C/C++ 等)或者 Java 虚拟机( Java 系语言)来管理,对程序员是不可见的,当然我们可以通过配置参数来调整程序的栈空间大小,但不免麻烦,并且递归层数一增加,栈很可能又要溢出。 尾递归是一个常用的优化方法,很多语言在执行的时候会识别这种优化,因为递归函数调用是一个函数的最后一步,所以在递归调用之前,就可以把当前函数调用从栈中弹出,再把新的函数调用压栈,这样就不会因为递归深度的增加吃掉栈空间了。 但尾递归并不是很容易就能实现的,用二叉树的中序遍历举例,它的递归版本非常简单直观,