递归算法总结及C语言代码实现

本文主要受到宋劲松老师写的《Linux C编程》递归章节的启发。最能体现算法本质的算法就是递归。希望这篇文章对刚刚接触递归或者对递归感到困惑的朋友有所帮助。如有错误，还请各人生言专家指正。二叉树的递归示例代码请参见仓库的binary_tree目录。本文的其他代码在这里。 ？嗯，强烈推荐！

递归的一个简单示例是求整数阶乘，n!=n*(n-1)!, 0!=1。然后你可以编写以下递归程序：

int factorial(int n)
{
	if (n == 0)
		return 1;
	else {
		int recurse = factorial(n-1);
		int result = n * recurse;
		return result;
	}
}
复制代码

factorial 该函数是一个递归函数，它调用自身。直接或间接调用自身的函数称为递归函数。 如果您感到困惑，您可以将阶乘（n-1）步骤视为调用另一个函数 - 具有相同函数名称和相同代码的另一个函数。调用它意味着跳转到它的代码执行，然后返回到阶乘（n-1）并继续该调用的下一步。

为了证明递归算法的正确性，我们可以一步步来看看执行结果。记得刚开始学递归算法的时候，总有张二和尚摸不着头脑的感觉。当时我一直想按照递归一步步看执行结果。当递归层数较少时，很容易处理，但当层数较多时，就会变得混乱，你不知道自己遵循了哪一层递归。比如计算阶乘的时候，如果只跟着阶乘（3）问题不大，但是如果跟着阶乘（100）那就真的很麻烦了。

其实我们不需要查看每个函数就能看到执行结果。例如，当我们在自己的函数中调用 printf 函数时，我们不会介入查看它是如何打印的，因为我们相信它已经完成了。打印工作。 当我们编写阶乘函数时，我们有以下代码：

int recurse = factorial(n-1);
int result = n * recurse;
复制代码

此时，如果我们认为阶乘是正确的，那么传递参数 n-1 就会返回 (n-1)! ，那么result =n* (n-1)!=n!，所以这是阶乘(n)的结果。

当然，这有点奇怪：我们还没有写完阶乘函数，为什么我们要相信阶乘(n-1)是真的呢？ 如果你相信你正在写的递归函数是正确的，调用它，然后最终基于此编写递归函数，那么它就是正确的，并且将成为你相信它是正确的。

这话说起来还是有点神秘。让我们从数学上严格证明阶乘函数的正确性。刚才说了，factor(n)的正确性取决于factor(n-1)的正确性。只要后者为真，将后者的结果乘以 n 并返回。因此，证明factor(n)的正确性就是证明factorial(n-1)的正确性。同理，我们要证明factorial(n-1)的正确性，的正确性就是factorial(n-2)的正确性，以此类推，最后：证明factor(1)的正确性就是factor(0)的正确性。 factor(0) 的正确性不依赖于其他函数调用。它是程序中的一个小分支。 返回1；这个1是根据阶乘的定义写的。 ，肯定为真，所以 factor(1) 的实现为真，因此 factoral(2) 也为真，依此类推，最后 ) 也是正确的。

其实这是中学时所教授的数学入门方法。用数学归纳法证明，只需要证明两点：基本情况正确，递归关系正确。在写递归函数的时候，一定要记得写一个base case，否则，即使递归关系正确，整个函数也不会正确。如果阶乘函数错过基本情况，则会导致无限循环。

2 递归经典问题

从上一节求阶乘的简单例子的讨论中，我们可以了解递归算法的本质：从功能上理解函数的同时，你必须相信你写的函数是正确的，如果你基于此调用它，那么它就是正确的。 我们从一些常见的算法题来看如何理解递归。这是我的一些理解。欢迎任何人提出更好的方法。

2.1）汉诺塔问题

问题： 汉诺塔问题是一个常见问题。表示一座塔A上有n块不同大小的盘子，从下到上，顺序是从小到大依次排列的。需要将所有n块瓷砖移动到另一个塔C。可以用B塔进行转移，但必须满足任何时候大盘不放在小盘上。

说明：基本思路分为三步。首先将最上面的 N-1 个盘子通过 C 移动到 B，然后将下面的 N-1 个盘子移动到 C，然后将 B 上的 N-1 个盘子通过 C 移动。A 移动到 C。总时间复杂度为 f(n ) )=2f(n-1)+1，所以 f(n)=2^n-1。

/**
 * 汉诺塔
 */
void hano(char a, char b, char c, int n) {
    if (n <= 0) return;

    hano(a, c, b, n-1);
    move(a, c);
    hano(b, a, c, n-1);
}

void move(char a, char b)
{
    printf("%c->%c\n", a, b);
}
复制代码

2.2）求二叉树的深度

这里的深度是指二叉树从根节点到叶子节点的最大高度。例如，如果只有一个节点，则深度为1。如果有N层，则高度为N。

int depth(BTNode* root)  
{  
    if (root == NULL)  
        return 0;  
    else {  
        int lDepth = depth(root->left);  //获取左子树深度  
        int rDepth = depth(root->right); //获取右子树深度  
        return lDepth>rDepth? lDepth+1: rDepth+1; //取较大值+1即为二叉树深度  
    }  
}  
复制代码

那么从功能上如何理解函数Depth呢？我们可以知道，定义这个函数的目的是求二叉树的深度。也就是说，如果我们完成函数深度，那么深度(root)就可以正确返回以root为根的二叉树的深度。因此，在我们的代码中，深度（root->left）返回左子树的深度，深度（root->right）返回右树的子深度。虽然此时我们还没有写完深度函数，但是我们相信深度函数能够正确完成该功能。因此，我们得到lDepth和rDepth，然后通过比较返回较大的值加1作为二叉树的深度。

如果很难理解，你可以想象一下叫深度（root->left）的函数，而深度是另一个同名的函数，执行相同的功能，这样更容易理解。请注意基本情况，这里是当 root == NULL 时，深度为 0，函数返回 0。

2.3）判断二叉树是否平衡

平衡二叉树是指每个节点左右子树的深度差不大于1。判断二叉树是否平衡可以实现e递归算法。

int isBalanceBTTop2Down(BTNode *root)
{
    if (!root) return 1;

    int leftHeight = btHeight(root->left);
    int rightHeight = btHeight(root->right);
    int hDiff = abs(leftHeight - rightHeight);

    if (hDiff > 1) return 0;

    return isBalanceBTTop2Down(root->left) && isBalanceBTTop2Down(root->right);
}
复制代码

该函数的功能定义是二叉树根是平衡二叉树，即其所有节点的左右子树的深度差不大于1。首先判断是否根节点满足条件。如果不是，则立即返回 0。如果满足，则必须判断左子树和右子树是否都是平衡二叉树。如果两者都是，则返回1，否则返回0。

2.4）置换算法

置换算法也是一种递归模型。我记得当我第一次看到代码一层一层的时候，我的心都被震撼了。现在从函数功能的角度来看确实容易理解很多。我们先看代码：

/**
 * 输出全排列，k为起始位置，n为数组大小
 */
void permute(int a[], int k, int n)
{
    if (k == n-1) {
        printIntArray(a, n); // 输出数组
    } else {
        int i;
        for (i = k; i < n; i++) {
            swapInt(a, i, k); // 交换
            permute(a, k+1, n); // 下一次排列
            swapInt(a, i, k); // 恢复原来的序列
        }
    }
}
复制代码

首先要明确的是perm(a, k, n)函数的功能：数组和位置k out的所有排列，以及数组长度为n。这样，当我们调用程序时，调用格式为perm(a, 0, n)，即输出从位置0开始的数组的所有排列，即所有排列数组。基本条件是k==n-1。此时已经到达最后一个元素，第一个排列完成，立即发出。否则，将位置k开始的每个元素与位置k的值进行交换（包括与自身交换），然后进行下一次排列。排列完成后，记得恢复原来的顺序。

假设数组大小为N=3，程序调用Perm(a, 0, 3)可以这样理解：第一次交换0, 0，Perm(a, 1, 3 ) ) 执行完毕，执行后再次交换0。 ，0，此时数组恢复到初始值。第二次交换1.0（注意此时数组为初始值），执行perm(a,1,3)。执行完后，再次交换1.0，数组就会恢复到初始值。第三次交换2, 0，进行烫发(a, 1, 3)。执行完成后，交换2、0，数组返回初始值。

从功能的角度来看，这意味着首先是 0。设置位置，然后调用perm(a, 1, 3)从1开始排列，这样就可以排除所有排列。第0个位置可能的值为a[0]、a[1]、a[2]。这样通过交换保证了第0个位置可能的值。请记住每次交换后恢复初始值。

例如数组a={1,2,3}，则程序输出结果为：1 2 3, 1 3 2, 2 1 3, 2 3 3 2 1、3 1 2。即先输出以1为第一值的排列，然后输出以2和3为第一值的排列。

2.5）组合算法

组合算法也可以递归实现，但其原理与0-1背包问题类似。也就是说，您可以投票也可以不投票。请注意，您不能选择重复的数字。完整代码如下：

/*
 * 组合主函数，包括选取1到n个数字
 */ 
void combination(int a[], int n)
{
    int *select = (int *)calloc(sizeof(int), n); // select为辅助数组，用于存储选取的数
    int k;
    for (k = 1; k <= n; k++) {
        combinationUtil(a, n, 0, k, select);
    }
}

/*
 * 组合工具函数：从数组a从位置i开始选取k个数
 */
void combinationUtil(int a[], int n, int i, int k, int *select)
{
    if (i > n) return; //位置超出数组范围直接返回，否则非法访问会出段错误

    if (k == 0) {  //选取完了，输出选取的数字
        int j;
        for (j = 0; j < n; j++) {
            if (select[j])
                printf("%d ", a[j]);
        }
        printf("\n");
    } else {
        select[i] = 1;  
        combinationUtil(a, n, i+1, k-1, select); //第i个数字被选取，从后续i+1开始选取k-1个数
        select[i] = 0;
        combinationUtil(a, n, i+1, k, select); //第i个数字不选，则从后续i+1位置开始还要选取k个数
    }
}
复制代码

2.6）倒序打印字符串

这个比较简单，代码如下：

void reversePrint(const char *str) 
{
    if (!*str)
        return;

    reversePrint(str + 1);
    putchar(*str);
}
复制代码

2.7）链表倒序

链表倒序 List我们将使用迭代来实现它，但是如果我们想要唯一地单独进行，则可以使用递归，如下所示。代码请参见仓库的aslist目录。

/**
 * 链表逆序，递归实现。
 */
ListNode *listReverseRecursive(ListNode *head)
{
    if (!head || !head->next) {
        return head;
    }

    ListNode *reversedHead = listReverseRecursive(head->next);
    head->next->next = head;
    head->next = NULL;
    return reversedHead;
}
复制代码

参考文献

• 宋劲松与老师《Linux C编程》递归篇
• 数据结构与算法-C语言实现

作者: ssjhustets:ssjhustets