递归算法主要寻找：
终止条件：递归的尽头。
单级递归的行为：在一次递归里要做的事情。
返回值：每次迭代要return的东西。
例题
求二叉树的深度
class Solution {
public int maxDepth(TreeNode root) {
//终止条件：当树为空时结束递归，并返回当前深度0
if(root == null){
return 0;
}
//root的左、右子树的最大深度
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
//返回的是左右子树的最大深度+1
return Math.max(leftDepth, rightDepth) + 1;
}
}
两两交换链表中的节点
例如
给定 1->2->3->4, 你应该返回 2->1->4->3.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
//根据第二步：返回给上一级的是当前已经完成交换后，即处理好了的链表部分
return next;
}
}
反转链表
首先，假定方法是已经实现的。
终止条件为：当当前节点(传了空节点)或下一节点（传了单节点）为空，则无需反转返回当前节点。
递归行为：假定之后的节点均已实现反转，则需要将已经反转的尾部的next变为当前节点，而当前节点由于是第一个节点，其next为null。此处注意在反转前需要先留存反转后的尾部；
返回值：返回反转后的头结点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
//终止条件
if(head==null||head.next==null){
return head;
}else{
//保留尾部以便于head节点使用
ListNode tmp = head.next;
//剩余节点反转后的头，其实也是最终的头
ListNode newHead = reverseList(head.next);
tmp.next = head;
head.next = null;
return newHead;
}
}
}