递归---从台阶问题学习递归、递归优化和非递归

电玩女神 2023-06-17 06:57 5阅读 0赞

> 递归就是将大问题划分为若干个子问题，各个问题是嵌套关系，最小的那个问题的结果是已知的，大问题不断分解直到达到最小问题的过程叫做“递”，小问题的解释已知的，然后根据这个解回过去求大问题的解的过程叫做“归”。

最简单的递归的例子就是求n的阶乘：  
其递推公式为：f(n) = n \* f(n-1)，其中，f(1) = 1

#### 递归需要满足三个条件 ####

1.  一个问题的解可以分解为几个子问题
2.  这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
3.  存在递归终止条件

#### 编写递归代码 ####

1.  找到规律
2.  写出递推公式
3.  找到终止条件
4.  用简单的例子验证

比如这个问题：假如这里有n个台阶，每次你可以跨1个台阶或者2个台阶，请问走这n个台阶有多少种走法？如果有7个台阶，你可以2，2，2，1这样子上去，也可以1，2，1，1，2这样子上去，总之走法有很多，那如何用编程求得总共有多少种走法呢？  
**找到规律**  
这个问题可以根据第一步的走法把所有走法分为两类，第一类是第一步走了1个台阶，另一类是第一步走了2个台阶。所以n个台阶的走法就等于先走1阶后，n-1个台阶的走法 加上先走2阶后，n-2个台阶的走法。  
**写出递推公式**  
用公式表示就是：

f(n) = f(n-1)+f(n-2)

**找到终止条件**  
当n为1的时候，就只有一种走法，即f(1)=1  
**用简单的例子验证**  
假设n=2，根据递推公式f(2) = f(1) + f(0)，其实f(0)并不合理，因此重新思考下终止条件，应该是:

f(1)=1;f(2)=3

代码实现1：

class Solution { 
        private $result = [];
        /** * @param Integer $n * @return Integer */
        function climbStairs($n) { 
            if(1 == $n) return 1;
            if(2 == $n) return 2;
    
            $ret = $this->climbStairs($n - 1) + $this->climbStairs($n - 2);
            return $ret;
        }
    }

#### 编写递归代码容易遇到的问题及解决办法 ####

1.堆栈溢出  
函数调用会使用栈来保存临时变量等信息，每调用一个函数，就会将临时变量封装为栈帧压入栈顶，等函数执行完成返回时，将该次函数调用所用的信息从栈顶弹出。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。

**解决方案**：  
可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度（比如1000）之后，我们就不继续往下再递归了，直接返回报错。在递归的时候可以用一个静态变量用作递归深度的计数器。

2.重复计算问题  
递归会出现重复计算的问题，比如台阶问题，f(5)=f(4)+f(3)，f(3)会被计算一次，当f(4)分解为f(3)+f(2)的时候，f(3)又会被计算一次。

**解决方案**：  
可以用一个数据结构将已经计算的结果保存起立，当再次使用到该结果的时候就可以直接返回。以台阶问题举例：  
代码实现2：

class Solution { 
        private $result = [];
        /** * @param Integer $n * @return Integer */
        function climbStairs($n) { 
            if(1 == $n) return 1;
            if(2 == $n) return 2;
    
            if(isset($this->result[$n])) { 
                return $this->result[$n];
            }
    
            $ret = $this->climbStairs($n - 1) + $this->climbStairs($n - 2);
            $this->result[$n] = $ret;
            return $ret;
        }
    }

3.时间效率和空间效率  
递归的调用深度很深的时候，会积聚一个较大的时间成本和空间成本。

#### 将递归代码改写为非递归代码 ####

递归有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以，在开发过程中，我们要根据实际情况来选择是否需要用递归的方式来实现。  
代码实现3：

class Solution { 
        private $result = [];
        /** * @param Integer $n * @return Integer */
        function climbStairs($n) { 
            if(1 == $n) return 1;
            if(2 == $n) return 2;
    
            $pre = 2; //前一个子问题的解
            $prepre = 1;//前一个子问题的子问题的解
            $ret = 0; //当前问题的解
    
            for($i=3; $i<=$n; ++$i) { 
                $ret = $pre + $prepre;
                $prepre = $pre;
                $pre = $ret;
            }
            return $ret;
        }
    }

#### 台阶问题三种解法的比较 ####

test1.php是未经优化的递归解法  
test2.php是优化过的递归解法  
test3.php是非递归解法  
n=40  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191127232223106.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70