深究递归和迭代的区别、优缺点及实例对比

我会带着你远行 2022-12-14 13:46 157阅读 0赞

### 目录 ###

*  1.迭代是人，递归是神！
 *  2.递归
 *   *  2.1构成递归需具备的条件：
     *  2.2递归的基本原理
     *  2.3递归优缺点
 *  3.例题：走楼梯
 *   *  3.1题目描述：
 *  4.求n!递归法
 *  5.求n!迭代法
 *  6.迭代

# 1.迭代是人，递归是神！ #

从“编程之美”的角度看，可以借用一句非常经典的话：“迭代是人，递归是神！”来从宏观上对二者进行把握。

从概念上讲，递归就是指程序调用自身的编程思想，即一个函数调用本身；迭代是利用已知的变量值，根据递推公式不断演进得到变量新值得编程思想。

# 2.递归 #

递归就是函数自己调用自己。

## 2.1构成递归需具备的条件： ##

子问题须与原始问题为同样的事，且更为简单；  
不能无限制地调用本身，须有个出口，化简为非递归状况处理。

## 2.2递归的基本原理 ##

第一：每一级的函数调用都有自己的变量。

第二：每一次函数调用都会有一次返回。

第三：递归函数中，位于递归调用前的语句和各级被调用函数具有相同的执行顺序。

第四：递归函数中，位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反。

第五：虽然每一级递归都有自己的变量，但是函数代码并不会得到复制。

## 2.3递归优缺点 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb2Vyc29uZw_size_16_color_FFFFFF_t_70_pic_center]

2.4编写一个递归函数  
这个递归函数的功能是什么，怎样调用这个函数，即设计好递归函数的返回值和参数列表  
什么时候应该结束这个递归，它的边界条件（出口）是什么（边界条件）  
在非边界情况时，怎样从第n层转变成第n+1层（递推公式）  
例：

int f(int n) { 
    　　//出口
        if (n > 0) { 
            return n + f(n - 1);
        } else { 
            return 0;
        }
    }

解析:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb2Vyc29uZw_size_16_color_FFFFFF_t_70_pic_center 1]

具体步骤：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb2Vyc29uZw_size_16_color_FFFFFF_t_70_pic_center 2]

***递归递归，有递就得有归（出口），只递不归会导致程序崩溃。***

要得到n - 1的积直接调用 f(x) 这个函数就行了，完全不需要思考这个函数怎么执行的。

# 3.例题：走楼梯 #

## 3.1题目描述： ##

一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法。I第一行输入T，表示有多少个测试数据。接下来T行，每行输入一个数n，表示台阶的阶数。  
输出时每一行对应一个输出。

假如一共有三级台阶，一共有多少种走法？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb2Vyc29uZw_size_16_color_FFFFFF_t_70_pic_center 3]

假设有n级台阶，一共有多少种走法？  
![在这里插入图片描述][20201014082229727.png_pic_center]

当n > 2 时，如果走1级有多少种走法 + 如果走2级有多少种走法，就是n级台阶所有的走法。

# 4.求n!递归法 #

int fun(int n) { 
        if (n == 1) { 
            return 1;
        } else { 
            return n * fun(n - 1);
        }
    }

# 5.求n!迭代法 #

int fun(int n) { 
        int x = 1;
        for (int i = 2; i <= n; i++) { 
            x *= i;
        }
        return x;
    }

# 6.迭代 #

迭代与普通循环的区别是：迭代时，循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。  
递归与普通循环的区别是：循环是有去无回，而递归则是有去有回(因为存在终止条件)。

在循环的次数较大的时候，迭代的效率明显高于递归。

参考：  
[https://www.cnblogs.com/xiaozhongfeixiang/p/12093096.html][https_www.cnblogs.com_xiaozhongfeixiang_p_12093096.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb2Vyc29uZw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/82a2b4af15c04020ab14d7af0241955a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb2Vyc29uZw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/01d051d6fa9144e8a0182c103e2f2b28.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb2Vyc29uZw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/9fa3a3dda7344bb4ae3450bcfcfef03c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb2Vyc29uZw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/0b4bd45858fe497593233250ee0a9265.png
[20201014082229727.png_pic_center]: /images/20221123/325f86ded4ce4484944e4f905f4827cb.png
[https_www.cnblogs.com_xiaozhongfeixiang_p_12093096.html]: https://www.cnblogs.com/xiaozhongfeixiang/p/12093096.html