关于算法:递归理解

一. 分组问题

题目：用递归法计算从 n 集体当选选 k 集体组成一个委员会的不同组合数。
剖析：由 n 集体里选 k 集体的组合数 = 由 n - 1 集体里选 k 集体的组合数 + 由 n - 1 集体里选 k - 1 集体的组合数；当 n = k 或 k = 0 时，组合数为 1。

#include <iostream>
using namespace std;
/* 双递归的执行过程，能够借助二叉树构造来形容 */
int comm(int n, int k) {// 排除 n < k 的状况
    if (n < k) {return 0;}
    else if(n == k || k == 0)// 递归函数的进口
    {return 1;}
    else {// 两个递归深刻点，然而同函数中左右深刻点的深刻档次并不一定雷同
        return comm(n - 1, k) + comm(n -1, k - 1);
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << comm(n, k);
    system("pause");
    return 0;
}

二. 双递归函数的执行程序

双递归的执行过程，能够借助二叉树构造来形容：

1. 程序从首先左端的递归深刻点进入，再次调用函数 (4, 3)，再次从左侧深刻点(3, 3) 深刻。此时失去第一个递归的终止条件：n = k，组合数为 1，将 1 返回给父级节点；在此之前，(4, 3)右端的函数深刻点并未执行，而是作为没有执行结束的函数被保留在栈中。此时则是执行 (4, 3) 右侧递归深刻点 (3, 2) 函数。残余执行过程由红色箭头标识，不再一一阐明。
2. 无论执行左侧还是右侧函数，调用时必然先执行左子树所代表的函数。若此时这棵左子树仍然存在后辈，则先执行它的左子树函数，而后循环此逻辑；直到左子树没有上级节点时，那么就返回它的下级节点，来执行下级节点的右子树函数。
3. 应用二叉树示意的双递归函数执行过程中，任何一个节点若存在子节点，那么它的左后辈与右后辈必然是同时存在的。起因就在于在递归调用函数时，两个调用本身的函数也是同时存在的。
4. 当一个节点找到递归进口时，那么与它有雷同父级节点的兄弟节点不会进行递归深刻，直到失去一个能够返回的值为止 (即找到递归进口)。所以，叶子结点返回值逐级累加，所有的返回值之和，就是题目所求后果，也就是整个递归最外层函数的返回值即函数调用者(此题为 main 函数) 所须要的后果。
5. 能够应用断点调试对变量进行监督，从而更好地了解双深刻点递归函数的执行过程。