泛型递归、树的递归

泛型递归、树的递归

递归Recursion

• 递归-循环
• 通过函数体来进行循环

1. 从前有个山
2. 山里有个庙
3. 庙里有个和尚讲故事
4. 返回1

盗梦空间

• 向下进入到不同梦境中，向上又回到原来一层
• 通过声音同步回到上一层
• 每一层的环境和周围的人都是一份拷贝、主角等几个人穿越不同层级的梦境(发生和携带变化)

计算n!

def Factorial(n):
    if n<=1:
        return 1
    return n*Factorial(n-1)

factorial(6)
6factorial(5)
6(5factorial(4))
6(5(4factorial(3)))
6(5(4(3factorial(2))))
6(5(4(3(2factorial(1)))))
6(5(4(3(21))))
6(5(4(32))
6(5(46))
6(524)
6120
720

思维要点

1. 不要人头递归
2. 找到最近最简方法，将其拆解成可重复解决的问题(重复子问题)
3. 数学归纳法思维

LeetCode实战例题

爬楼梯

class Solution {
public:
    long long GetCni(int n, int i) {
        i = (n - i > i)? i : (n - i);
        if(i == 0) return 1;
        else return GetCni(n, i-1)*(n-i+1)/i;
    }
    int climbStairs(int n) {
        int i = 0;
        int Sum = 0;
        while(i <= n/2) {
            Sum += GetCni(n-i, i);
            i++;
        }
        return Sum;
    }
};

括号生成

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if(n==0)
            return res;
        if(n==1)
        {
            res.push_back("()");
            return res;
        }
        string s = "";
        for(int i = 0 ;i < n;++i)
            s+="()";
        sort(s.begin(),s.end());
        do{
            if(IsLegal(s))
                res.push_back(s);
        }while(next_permutation(s.begin()+1,s.end()));
        return res;
    }
    bool IsLegal(string& s)
    {
        int count = 0;
        for(int i = 0;i < s.size();++i)
        {
            if(s[i]=='(')
                count++;
            else
                count--;
            if(count<0)
                return false;
        }
        return true;

    }
};