一、算法理解

严格来说，递归不是一种算法，而是一种解题思路。
递归的核心思想：将大问题分解为小问题来求解，然后再将小问题分解为更小的问题。这样一层一层地分解，直到问题规模被分解得足够小，不用继续分解，可以直接计算结果为止。

二、适用场景

（1）求f(n)
（2）可以做出f(n)与f(n-1)、f(n-2)...的规律

三、使用注意事项

使用递归，需要分析出：

1. 【求解目标】：f(n)
2. 【递归公式】：∑f(n)到∑f(n-1)/∑f(n-2)..的规律：对原始问题建模，找到大问题 分解成 小问题 的规律，即递归公式。
3. 【终止条件】：即把问题分解大足够小，不用继续分解的条件。

【注1】：f(n)与∑f(n)
一些用到递归的题目中，可能f(n)即∑f(n)。
但是，一些题目中，经常不是直接的f(n)=f(n-1)...f(n-2)...关系。而是：∑f(n)=∑f(n-1)/∑f(n-2)... ; f(n)=...∑f(n) 的关系。
详见如下“细胞分裂”样例。

【注2】：递归中缓存的使用
递归中∑f(n)=∑f(n-1)/∑f(n-2)...，扩展后：
∑f(n)=∑f(n-1)/∑f(n-2)...
∑f(n-1)=∑f(n-2)/∑f(n-3)...
...
不同深度的递归，∑f(n-2)、∑f(n-3)....会重复计算。为了提高效率，可以考虑缓存：
（1）计算∑f(x)时，把∑f(x)结果缓存起来。
(2）后续在调用到∑f(x)，直接从结果返回

如：如下递归关系f(n) = f(n-1) + f(n-2)

f(6) =         f(5)         +        f(4)
?             /    \                 /   ?         f(4)     f(3)            f(3)    f(2)
?        /  \      /   \           /   ?      f(3) f(2) f(2)  f(1)     f(2)  f(1)

四、场景样题场景思路

1.阶乘函数

f(6) = 6*5*4*3*2*1

求解f(n)。

【思路】：

1. 递归公式：f(n) = n*f(n-1)
2. 终止条件：f(1) = 1；

【实现代码】：

int count(int n) {
    //终止条件
    if (n == 1) {
       return 1;
    }
    //递归公式
    return n*count(n - 1);
}

2. 爬台阶/青蛙跳

爬台阶：有n级台阶，每次可以爬 1个台阶 或 2 个台阶。求：有多少种不同的方法可以爬到楼顶呢？

青蛙跳：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求：该青蛙跳上一个 n 级的台阶总共有多少种跳法。

如上两题相同。

【思路】：

由于每次只能爬1阶、或2级阶梯。所以跳上第n个台阶有两种选择：（1）调整第n-

个台阶后，再跳1个台阶；（2）跳上第n-2台阶后，再条2个台阶。即：

1. 迭代规律：f(n) = f(n-1) + f(n-2)
2. 终止条件：f(1) = 1; f(2) = 2;

【实现样例】

public int jumperCount(int n) {
    //数组作为缓存，f(x)数据缓存在数组n位置。初始值全是0
    int[] cache = new int[n + 1];
    
    return climb(n, cache);
}

public int jumper(int n, int[] cache) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    
    //f(x)有缓存，直接返回
    if (cache[n] > 0) {
        return cache[n];
    }
    
    //f(x)计算结果同时放入缓存中
    cache[n] = climb(n - 1, cache) + climb(n - 2, cache);
    return cache[n];
}

3. 斐波那契数列

1，1，2，3，5，8，13，21，34，55，....。这个数列从第3项开始，每一项都等于前两项之和。

【思路】：

1. 递归公式：f(n) = f(n-1) + f(n2)
2. 终止条件：f(1) = 1; f(2) = 1;

4. 细胞分裂

有一个细胞，每一个小时分裂一次，一次分裂一个子细胞，第三个小时后会死亡。那么n个小时之后有多少细胞？

【思路】

对问题进行建模：

可以看到细胞总数规律：

第一小时：1

第二小时：2

第三小时：4

第四小时：6

第五小时：10

......

总数上来看，规律不是很明显。

换个思路：既然细胞只能分裂2次，第三个小时死亡。那么：在第n个小时新分裂的细胞，一定是都n-1和n-2小时新分裂出来的。（n-3小时新分类的细胞，到第n小时就消亡了）。即：

第n小时新分裂出的细胞f(n) = f(n-1) + f(n-2)。

因为细胞分裂是1分2，所以第n小时细胞总数就是2*f(n)。

所以：

1. 递归公式：n小时新分裂数f(n) = f(n-1) + f(n-2)
2. 终止条件：第1小时新细胞数：f(1) = 1； 第2小时新细胞数f(2) = 1;

实现代码就是：

public int sumCell(int n) {
    //第1小时没分裂，直接返回
    if (n == 1) {
            return 1;
    }

    //数组作为缓存，f(x)数据缓存在数组n位置。初始值全是0
    int[] cache = new int[n + 1];
    
    return 2* newCell(n, cache);
}

//递归第n小时新分类细胞数
public int newCell(int n, int[] cache) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 1;
    }
    
    //f(x)有缓存，直接返回
    if (cache[n] > 0) {
        return cache[n];
    }
    
    //f(x)计算结果同时放入缓存中
    cache[n] = newCell(n - 1, cache) + newCell(n - 2, cache);
    return cache[n];
}

5. 反转二叉树

反转二叉树的左右节点。

【思路】

递归公式：reverse(root) ==> 先反转子树reverse(root->left) ; reverse(root->right)；反转root的left、right子节点。

终止条件：反转的节点为null。

6. 路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

【思路】：

递归公式：判断root-叶子之和是否存在f(node)=SUM---->判断左节点-叶子之和是否存在f(node->left)=SUM-root、或 右节点-叶子之和是否存在f(node->right)=SUM-root

终止条件：到叶子节点 刚好等于递减后的值。

注意：

1. 可能存在Node，只有左子树、或只有右子树。要注意判空。
2. 节点值可能是负数。

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) {
            return false;
        }    

        if(root.left == null && root.right == null) {
           if(targetSum == root.val) {
              return true;
           }
           else {
               return false;
           }
        }

        boolean ret = hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
        return ret;
    }
}

【算法】递归

原文：https://www.cnblogs.com/yickel/p/14800621.html