如何写递归( 二 ) _递归

2.2.2 由上到下
假如我们换个思路，f(n) = f(n-1) + nf(n)=f(n?1)+n 中我们把 f(n-1)f(n?1) 的结果（中间变量）提取出来 f(n, SUM) = SUM + nf(n,SUM)=SUM+n，
每次计算都带着它，这样我们可以先计算，然后把计算好的结果传递给递归函数进行下一次计算，这个过程我们称为「由上到下」。
由上到下：在递归层级中，我们根据当前「函数参数」计算出一些值，并在递归调用函数时将这些值传给自身。（依赖函数参数）
/*** 模拟程序执行过程：* sum(5, 0)* sum(4, 5)* sum(3, 9)* sum(2, 12)* sum(1, 14)* 15* * 由上到下：最终从 5 + 4 + 3 + 2 + 1 计算...* 递归函数「末尾」部分调用自身，根据逻辑先进行计算，然后把计算的中间变量传递调用函数。* * 这种在函数末尾调用自身的递归函数叫做「尾递归」*/public int sum2(int n, int sum) {if (n < 2) return 1 + sum;sum += n;return sum2(n - 1, sum);}
由上到下-范式
寻找递归递推关系
创建新函数，将「由下到上-范式」中的最终结果计算依赖的中间变量提取为函数的参数
寻找递归基本情况，跳出时返回基本情况的结果与中间变量的计算结果（最终结果）
根据函数参数与中间变量重新计算出新的中间变量
修改参数
递归调用并返回（该处的返回由基本情况触发）
public 返回值 f(参数，中间变量) {if (基本情况条件) return 基本情况的结果与中间变量的计算结果;中间变量 = 根据参数与中间变量重新计算修改参数；return f(参数,中间变量);}
2.2.3 由下到上、由上到下的区别
两者最大的区别在于对中间变量的处理，参与计算的中间变量是参数提供的还是返回值提供的，这个过程最终决定了基本情况的返回值处理逻辑、递归函数的执行位置。
递归函数在计算前先找到基本情况再算还是先算再找基本情况，这个过程也就是「由下到上、由上到下」的本质差异。
2.3 优化递归函数
优化点总结为：
充分分析基本情况（跳出条件），避免临界值跳不出递归，导致栈溢出。
分析递归深度，太深的递归容易导致栈溢出。
分析是否有重复计算问题，主要分析函数参数值是否会出现重复，直接代入递归的递推关系中运算即可。如果会出现重复使用数据结构记录。
比如：斐波那契数列 f(n) = f(n-1) + f(n-2)f(n)=f(n?1)+f(n?2)，如果直接采用该公式进行递归会重复计算很多表达式。如下图
分析数据溢出问题
将「由下到上」优化为「由上到下」，再改写为尾递归，再退化为循环结构。因为递归会对栈及中间变量的状态保存有额外的开销。
2.4 改为循环
递归本身的风险比较高，实际项目不推荐采用。部分编程语言可以对尾递归进行编译优化（优化为循环结构），比如 Scala 语言。但是部分语言不支持，比如 Java 。
函数式编程时推荐尾递归写法并加标识让编译器进行优化，下面是 Scala 语言优化的案例：
// Scala 编译前的尾递归写法，并注解为尾递归@scala.annotation.tailrecdef sum2(n: Int, sum: Int): Int = {if (n < 2) return sum + nsum2(n - 1, sum + n)}// 编译后优化为循环结果public int sum2(int n, int sum) {while (true) {if (n < 2) return sum + n; sum += n;n--;} }
一个不是尾递归的案例：
// 并不是最后一行递归调用就是尾递归，下面例子其实是一个由下到上的递归写法，返回值与 n 有关。def sum(n: Int): Int = {if (n < 2) return nreturn n + sum(n - 1) }
3. 案例实战-递归乘法
对于有些算法，递归比循环实现简单，比如二叉树的前中后序遍历。但是大部分时候循环比递归更直观更容易理解。