递归总结

递归三大要素

第一要素：明确这个函数想要干什么

这个函数的功能是什么，不管代码怎么实现，先明确这个函数是用来干什么的。

第二要素：寻找递归结束条件

我们需要找出当参数为啥时，递归结束，然后返回结果。我们必须更具这个参数的值，能够知道函数的结果是什么。

第三要素：找出函数的等价关系式

我们要不断缩小参数的范围，搜小之后，我们可以通过一些辅助的变量或操作，使原函数的结果不变。

案例1：斐波那契数列

int f(int n) {
    if(n <= 2)
        return n;
    return f(n-1) + f(n-2);
}

案例2：青蛙跳台阶

int f(int n) {
    if(n <= 2)
        return n;
    return f(n-1) + f(n-2);
}

案例3：反转单链表

class Node {
    int data;
    Node next;
}
Node reverseList(Node head) {
    if(head == null || head.next == null)
        return head;
    Node newNode = new Node();
    newNode = reverseList(head.next);
    
    head.next.next = head;
    head.next = null;
    return newNode;
}

递归优化思路

1、考虑是否重复计算

把中间的计算结果保存起来，下次进行计算时，判断是否计算过，如果计算过，直接取出来使用就行了，没有计算过，再递归计算。

2、考虑是否可以自底向上

当n比较大时，从上往下递归可能会导致栈空间不太够用，这种情况可以考虑自底向上的做法，也叫做递推。