1. 递归的定义
编程语言中，函数 Func(Type a,……)直接或间接调用函数本身，则该函数称为「递归函数」 。
在实现递归函数之前，有两件重要的事情需要弄清楚:
递推关系：一个问题的结果与其子问题的结果之间的关系 。
基本情况：不需要进一步的递归调用就可以直接计算答案的情况 。可理解为递归跳出条件 。
一旦我们计算出以上两个元素，再想要实现一个递归函数，就只需要根据递推关系调用函数本身，直到其抵达基本情况 。
1.1 递推关系
下面的插图给出了一个 5 行的帕斯卡三角，根据上面的定义，我们生成一个具有确定行数的帕斯卡三角形 。
首先，我们定义一个函数 f(i, j)f(i,j)，它将会返回帕斯卡三角形第 ii 行、第 jj 列的数字 。可以看到，每行的最左边和最右边的数字是基本情况，它总是等于 11 。
每个数是它左上方和右上方的数的和 。
递推关系：f(i, j) = f(i - 1, j - 1) + f(i - 1, j)f(i,j)=f(i?1,j?1)+f(i?1,j)
基本情况：f(i,j) = 1f(i,j)=1，当 j=1j=1 或者 i=ji=j 时 。
1.2 尾递归
尾递归：函数中所有的递归形式都出现在函数末尾时 。
递归函数的编写看起来比较难，其实是有套路可寻的，本问总结了写递归的一些范式技巧并在后续实战中进行验证 。
2. 如何写出一个递归函数
下面我们以累加的示例说明写递归的思路 。
1 + 2 + 3 + 4 + ... + n1+2+3+4+...+n，函数表达式为 f(n) = f(n-1) + nf(n)=f(n?1)+n
2.1 寻找基本情况
累加示例中，基本情况为 n = 1n=1 时，f(1) = 1f(1)=1 。
你也可以设定为 f(2) = 1 + 2 = 3f(2)=1+2=3，只要能正确跳出递归即可 。
2.2 寻找递推关系（难点）
【如何写递归】累加示例中，递推关系为 f(n) = f(n-1) + nf(n)=f(n?1)+n，f(n)f(n) 每次执行时依赖 f(n-1)f(n?1) 的结果，所以我们把 f(n-1)f(n?1) 的结果看作是中间变量 。
中间变量其实就是联系递归函数的纽带，分析出中间变量递归函数也就实现了 80% 。
大白话：当前结果必须借助前一个结果，前一个借助前前一个... 一直到时我们找到了「基本情况」 。
然后拿到「基本情况」开始往回计算 。这个过程我们简称为「由下到上」 。
下面我们用 f(5) = 1 + 2 + 3 + 4 + 5 = 15f(5)=1+2+3+4+5=15 这个过程进行分析 。
2.2.1 由下到上
由下到上：在每个递归层次上，我们首先递归地调用自身，然后根据返回值进行计算 。（依赖返回值）
/** * 模拟程序执行过程：* 5 + sum(4)* 5 + (4 + sum(3)* 5 + 4 + (3 + sum(2))* 5 + 4 + 3 + (2 + sum(1))* ------------------> 到达基本情况 sum(1) = 1，开始执行 ③ 行代码* 5 + 4 + 3 + (2 + 1)* 5 + 4 + (3 + 3)* 5 + (4 + 6)* (5 + 10)* 15* * 由下到上：最终从 1 + 2 + 3 + 4 + 5 计算...* 递归函数「开始」部分调用自身，这个过程就是找到基本情况），然后根据返回值进行计算 。*/public int sum(int n) {if (n < 2) return n;// ① 递归基本情况int childSum = sum(n - 1); // ② 寻找基本情况return n + childSum;// ③ 根据返回值运算}
由下到上的过程其实是一个先寻找基本情况（跳出条件），然后根据基本情况计算它的父问题，一直到最后一个父问题计算后，返回最终结果 。
本示例中基本情况是 sum(1) = 1，基本情况的父问题是 sum(2) = 2 + sum(1) 。
由下到上-范式
寻找递归递推关系
寻找递归基本情况，跳出时返回基本情况的结果
修改递归函数的参数
递归调用并返回中间变量
使用递归函数的返回值与当前参数进行计算，并返回最终结果
public 返回值 f(参数) {if (基本情况条件) return 基本情况的结果;修改参数；返回值 = f(参数); 最终结果 = 根据参数与返回值计算return 最终结果;}