递归算法 -一个渣渣

文章目录

递推方程递归与数学归纳法
递归算法设计的一般步骤

引言：

在玩俄罗斯套娃的时候你打开一个，看到里面还有一个套娃。再次打开发现还可以用同样的操作再次打开它，拿开套娃发现还有一个。若干次之后，你打开面前的套娃，这是最后一个了。然后，你开始从里往外复原，每盖上一个套娃，你就数一次，盖到最外层的时候，你可以回答出你到底打开了几个套娃。（貌似比钥匙开门的例子差点）

什么是递归：

递归算法通常是把一个大的复杂问题层层转化为一个或多个与原问题相似的规模较小的问题来求解。递归策略只需要少量的代码就可以描述出解题过程所需要的多次重复计算，大大减少了代码量。（一种分而治之的算法设计方法）

即直接或间接的调用自身，调用时改动关键变量，直到变量符合边界条件时停止调用原路返回。

递归，包含了 ‘递’ 和 ‘归’，这正是递归思想的精华所在。举个简单的栗子，计算 n！的值，比较直接的方法是for循环

int Cal(int n){
    int ans = 1;
    for(int i = 0; i < n; ++i)
        ans *= x;
    return ans;
}

而使用递归

int Cal(int x)
{
    if(x == 1)//递归出口
       return  1;
    return x * cal(x-1);
}

递归调用的实现分两步走，一步是“分解过程”将大问题分解成小问题，直到递归出口然后执行第二步是“求值过程” 即已知小问题计算大问题。

写每一个递归函数的时候，都应该在写之前考虑清楚，哪里体现了“递”，哪里体现了“归”。例如上述递归的代码中，我们通过直接调用自身cal(x，ans)进行 ‘递去’，在调用过程中改变参数x，直到满足边界条件x == 1 时 ‘归来’ 逐层返回我们需要的答案。

递归与循环

相同点：
（1）都是通过控制变量的边界，来改变多个变量为了得到所需要的值，反复执行。
（2）都是按照预先设计好的推断实现某一个值求取；（循环要更注重过程，而递归偏结果些）

不同点：
（1）递归通常逆向思维居多，“递”和“归”不一定容易发现；而循环从初始，结束条件到循环变量，较容易表达。
（2）一般来说用循环能实现的，递归可以实现，但是能用递归实现的，循环不一定能。因为有些题目只注重循环的结束条件和循环过程，而结束条件不易表达，或只注重循环的次数而不注重循环的开始条件和结束条件。

递归优点：代码简洁、清晰，并且容易验证正确性。

递归缺点：1）运行需要较多次函数调用，如果调用层数较深，每次都要创建新的变量，需要增加额外堆栈开销，对执行效率有一定影响，占用过多的内存资源。

2）递归算法解题的运行效率较低。在递归调用的过程中系统为每一层的返回点、局部变量等开辟了栈来储存。递归次数过多容易造成栈溢出等

何时使用递归

能够用递归解决的问题一般满足以下3个条件：

1. 问题可转化为一个或多个子问题，且子问题的求解方法与原问题完全相同，仅仅是在数量和规模上不同。（递归体）

2. 递归调用的次数必须有限。

3. 必须有结束递归的条件来中制递归。（递归出口）

在以下三种情况下，常常使用递归策略

1.定义是递归的

许多的数学公式、数列、概念的定义是递归的。例如求n！，Fibonacci数列等。这些问题的求解过程是可以将其递归定义转化为对应的递归算法的。例如上述的求n！的代码。

2.数据结构是递归的

许多数据结构的定义是递归的如树，链表等，所以我们在做关于树的算法题时往往可以采用递归的方法去接解题(常见树的遍历)。如单链表就是一种递归的数据结构，其节点类型定义如下：

typedef struct LNode{
    ElemType data;
    struct LNode * next;
}LinkList;

做个例题，求一个不带头结点的单链表L的所有data域之和的算法

int Sum(LinkList *L){
    if(L == NULL) //递归出口
        return 0;
    return (L->data + Sum(L->next)); //递归体
}

3.问题的求解方法是递归的

有些问题的解法也是递归的，最常见的就是汉诺塔问题。问题描述：设有三个分别命名为x，y，z的塔座，在塔座x上有n个直径各不相同的，从小到大按需要依次排列1 2 ....n的盘片，现要求将x塔座上的盘片移动到塔座z上，并仍按原序列叠放。

移动规则：每次只能移动一个盘片；盘片可以插在x,y,z中任何一座塔上；任何时候大盘片不能放在小盘片上。

汉洛塔问题可参考：https://blog.csdn.net/qq_37873310/article/details/80461767

递推方程递归与数学归纳法

数学归纳法是一种论证方法，递归法是算法与程序设计的一种实现技术，数学归纳法是递归的理论基础。

递归算法设计的一般步骤

递归算法求解过程的特征是：先将整个问题划分为若干个子问题，通过分别求解子问题，最后获得整个问题的解。

基于递归数据结构的递归算法设计

基于归纳法的递归算法设计

我们将大问题F(n)分解出小问题F(n-1)，求解F(n)和F(n-1)的方法和环境是相似的，但F(n)是一个“大问题”，而F(n-1)是一个“较小问题”，尽管F(n-1)还没有解决，但向解决目标靠近了一步，这就是一个“量变”，如此下次直到到达递归出口，便发生了“质变”，递归的问题便解决了。因此递归设计就是要找出合理的小问题，然后确定大问题的解与小问题之间的关系，即确定递归体。最后朝着此方向分解，必然有一个简单基本问题的解，以此作为递归出口。

递归算法转换为非递归算法

递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归运算要多。因此在求解问题的时候可以用递归思路去分析问题，用非递归算法求解问题。有两种方法：

1）直接转化法，不需要用栈，用循环结构的算法代替递归。直接转换法没有通用的转发算法，对具体的问题需要深入分析对应的递归结构，但特别是用尾递归以及单向递归。

2）间接转化法，需要用栈，用栈模拟系统的运行，通过分析只保存必须保存的值。对于非尾递归和单项递归难以用直接转化法，但所有的递归算法理论上都可以使用间接转化法转化为等价的非递归算法。

常见递归算法示例

简单排序、

冒泡排序、

n皇后问题

转载自原文链接, 如需删除请联系管理员。

原文链接：递归算法，转载请注明来源！

引言：