如何写递归( 五 ) _递归

由上到下的尾递归再优化为循环结构：（也称为动态规划）
public int numWaysFor(int n) {if (n < 2) return n;int i = 2; int a = 1; int b = 1; // 与尾递归 numWaysTailHelp 一致int count = a + b; // 保存次数，将尾递归的返回值提取为变量while (i <= n) { // 1-n 的过程// 因为 f(i) = f(i-1) + f(i-2) = a + b // 下次迭代时 f(i+1) = f(i) + f(i-1) = (a+b) + bcount = a + b;b = a;a = count;i++;}return count;}
5. 案例实战-合并两个有序的链表（多递推公式情况）
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输入：1->2->4, 1->3->4输出：1->1->2->3->4->4函数：public ListNode mergeTwoLists(ListNode l1, ListNode l2)链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
因为合并是一个条件判断的过程，因此我们在分析中要充分分析不同的条件分支。
基本情况：L1L1 或者 L2L2 有一个为空时，不为空的节点即为头节点
递推公式：因为合并时涉及条件判断，所以有两种递推公式
L1 >= L2L1>=L2 时：merge(L1,L2) = L1 + merge(L1.next,L2)merge(L1,L2)=L1+merge(L1.next,L2)，此时 L1L1 为头节点
L1 < L2L1 由下到上的范式验证：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (null == l1) return l2; // 基本情况，返回头节点if (null == l2) return l1; // 基本情况，返回头节点if (l1.val <= l2.val) { // 决定使用哪个递推公式ListNode mergeResult = mergeTwoLists(l1.next, l2); // 寻找基本情况l1.next = mergeResult;// 使用递归函数的返回值与当前参数进行计算，该处计算为链表链接指向return l1; // 返回计算后的头节点} else {ListNode mergeResult = mergeTwoLists(l1, l2.next); // 寻找基本情况l2.next = mergeResult; // 使用递归函数的返回值与当前参数进行计算，该处计算为链表链接指向return l2; // 返回计算后的头节点}}
当涉及到条件判断时，可能会出现多个基本情况、递推公式，我们在递归函数中逐一处理即可。
这个多公式案例理解让我们可以分析更为复杂递推关系，本质上就是范式的逐步套入、优化的过程。
6. 再谈由上到下、由下到上
一般情况，我们说递归时指的是「由下到上」，因为「由上到下」的过程往往需要创建新函数去完成，更甚至「由上到下」其实就是循环结构封装为函数式编程的写法，也叫尾递归。
由下到上转换为由上到下的过程其实就是转换为循环结构写法的过程。
递归难以理解的地方在于由下到上的过程，其实细化该难点可以分为「基本情况」->「改变参数继续递归」->「拿到递归返回值与当前参数计算」。
实际编码中我们只要按上述提到的范式进行代码编写，上述示例中的基本情况比较单一，中间变量也只涉及一个，对于复杂的跳出及中间变量的处理只要按范式步骤进行分析然后再优化一定可以写出一个递归函数。
对于递推关系的寻找过程，没有范式可寻，需要见多识广（::刷刷刷::），不断总结。
7. 递归算法推荐
力扣-递归标签相关算法
力扣-卡片-二叉树
力扣-卡片-递归 I
总结
简单的总结为：
你要写哪种类型的递归，从上算还是从下算，这决定了你如何确认递推关系
分析基本情况
寻找递推关系，在递推关系中提取中间变量
套入上文中的递归范式
按上文中的优化点进行优化
题外话：对于自上而下的计算不是必须创建新函数去传入中间变量，因为有时我们可以使用全局变量保存、或者直接修改当前递推关系中的变量即可。
推荐使用总结内容「由上到下、由下到上、循环结构」三种方法完成力扣-206. 反转链表