Question

递归转成非递归会怎样

Answer 1

我们一般对递归的印象就是一个函数反复的“自己调用自己”，代码精炼，便于阅读。但是，从本质上来说，递归并不是简单的自己调用自己，而是一种分析和解决问题的方法和思想。简单来说，递归思想就是：把问题分解成规模更小，但和原问题有着相同解法的问题。典型的问题有汉诺塔问题，斐波那契数列，二分查找问题，快速排序问题等。PS：其实像我们常见的分治法和动态规划法都是递归思想的经典应用。

既然的递归的思想是把问题分解成规模更小但和原问题有着相同解法的问题，那是不是所有具有这样特性的问题都能用递归来解决呢？答案是否定的。除了这个特性，能用递归解决的问题还必须具有一个特性：存在一种简单情境，能让递归在简单情境下退出，也就是要有一个递归出口。总结一下就是，能用递归解决的问题，必须满足以下两个条件：

• 一个问题能够分解成规模更小，且与原问题有着相同解的问题；

• 存在一个能让递归调用退出的简单出口。

比如，阶乘问题：fact(n) = n*fact(n-1)，当n = 1时，存在简单情境：fact(1) = 1。斐波那契数列问题：fib(n) = fib(n-1) + fib(n-2)，当n = 1和n = 2时，存在简单情境：fib(1) = 1, fib(2) = 1。上述两个问题仅存在一种简单情境，有些问题可能存在两种以上的简单情境（在写代码时务必都要考虑到），比如：二分查找问题：第一种简单情境是需要查找的元素与中值元素相等；第二种简单情境是：待查找的元素没在序列中，则通过比较待查找元素和最后一个划分的元素来确定结果。