递归的核心:对于一个节点来说,它只需要知道它之后的所有节点操作之后的结果就可以了。

个人总结三要素:

  • 确定递归函数的参数和返回值。
  • 确定终止条件。
  • 确定单个递归的内容。

例题

1,反转链表(递归,双指针 )

来自 LeetCode206

补充:

* public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }

解法

1,双指针/迭代

在双指针文章里。

2,递推

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }

    public ListNode reverse(ListNode pre,ListNode cur){
        if(cur == null)
            return pre;
        ListNode temp = cur.next;
        cur.next = pre;
        return reverse(cur,temp);
    }
}

pre为前项,cur为当前指针,temp为后项。

理解(不保证正确)

1,递归想对于迭代,代码会更加清晰一些。

2,递归分两种

  • 一种是return 递归式,求的是最后一个递归式的结果,作为整个函数的结果。
  • 一种是过程中递归式,更多是类似于动态规划,每一层递归都是给前一阵作为实现的基石。
  • 递归思想中,不应该考虑每一步递归的过程,这样大概率出错。应该考虑当前递归我需要得到的结果就可以了。(重点)

3,有关链表的题目,应该在本子上进行画图,会让思路更加清晰。

2,合并两个有序链表

来自LeetCode 21

解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val>l2.val)
        {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
        else
        {
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }
    }
}

理解

1,想到用递归做题有点难,想到后就很容易解决。

3,二叉树遍历

在算法(八)那篇文章里。

很重要。(不过递归算法太简单不是很重要)