C++入门教程（24）深入理解递归

调用

//假设蛇叔可以发动9次忍术
tu(9);

运行：

我吐我自己
我吐我自己
我吐我自己
我吐我自己
我吐我自己
我吐我自己
我吐我自己
我吐我自己
我吐我自己
我吐剑

运用递归可以解决很多实际的问题，比如一些复杂的问题，可以通过先将复杂问题拆解为n项运算，然后通过递归的方式，依次去求解，最终达到我们的目的，下面举例说明

假如有一手扑克牌，我们想知道这些扑克牌一共有哪些种组合，我们就可以通过递归的方式去实现。

每一张牌，都有被选取或不被选取两种可能

那么第一张牌会产生两种结果，选或者不选，如果我们知道后面的N种可能，那么最终结果就是

这N种可能，和N种可能加上这张牌 总共2N种可能

即：        选第一张 + fun(n-1)

                不选第一张+fun(n-1)

依次这样计算，直到剩下最后一张牌，我们就可以递归结束这个运算了。

//                     0
//                 /        \
//      a        0            a
//              /  \        /   \
//      b     0     b      a      a+b
//           / \   / \    / \    /   \
//      c   0   c b b+c  a a+c a+b  a+b+c
//                    ...
void fun(int i,vector cards,vectorresult,vector> &allResults)
{
    if (i== cards.size()) {
        if (result.size() > 0) {
            allResults.push_back(result);
        }
        return;
    }
    else{
        fun(i+1,cards,result,allResults);
        result.push_back(cards.at(i));
        fun(i+1,cards,result,allResults);
    }
    
}

//打印vector>
void printAllCards(vector> allResults)
{
    for(int i = 0; i< allResults.size();i++)
    {
        for (int j = 0; j< allResults.at(i).size(); j++) {
            cout<< allResults[i][j]<< " ";
        }
        cout<< endl;
    }
}

调用：

    vector myCards = vector{3,4,5,6,7};
    vector> allResults;
    vector result;
    fun(0,myCards,result,allResults);
    printAllCards(allResults);

运行：

7 
6 
6 7 
5 
5 7 
5 6 
5 6 7 
4 
4 7 
4 6 
4 6 7 
4 5 
4 5 7 
4 5 6 
4 5 6 7 
3 
3 7 
3 6 
3 6 7 
3 5 
3 5 7 
3 5 6 
3 5 6 7 
3 4 
3 4 7 
3 4 6 
3 4 6 7 
3 4 5 
3 4 5 7 
3 4 5 6 
3 4 5 6 7 

其实按道理每张牌都有2种可能，5张牌就是2的5次方，应该有32种可能，但是都不选的可能是不算在内的，所以只输出了31种情况

这种递归方式类似于构建一种树形的结构，然后依次遍历子节点， 直到叶子节点结束。

掌握这种解题的思路，可以方便以后学习动态规划，这种类型的问题，有时候找到递归的思路，往往程序实现起来就没什么难度了。

难点一般是如何抽象出这个可以递归的函数。

即怎样找到

        fun(n) = n的各种情况+f(n-1)

        n的各种情况不一定是2种，可以为0或者多 这样就是一个多叉树

另外，为了避免重复的运算，可以将已经算过的f(m)存起来。

这样就需要fun(n)有返回值,并且需要记录下递归到i得到的fun(i)值,如果再次调用到fun(i),就直接使用记录的值。