递归的妙用

递归算法是在函数或子过程的内部，直接或者间接地调用自己的算法。学过算法与数据结构的都知道，通过递归可以将一个复杂的问题化解为一个子问题和一个基本问题，从而达到简化问题逻辑的效果。本篇将通过几个例子来讲解一下递归的妙用。

链表中的递归

链表是一种具有天然递归结构的数据结构，将链表头去掉后，剩下部分仍然是一个链表。因此与链表有关的操作几乎都能用递归的方式解决。
以一道LeetCode上的题目为例来看一下递归的威力：

LeetCode203号题

这道题目是很简单的，正常的书写逻辑就可以达到想要的效果，在java语言下，系统给出的模板是这样的：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        
    }
}

我们需要在Solution内书写我们的逻辑完成想要达到的效果，在此之前，首先在自己的IDE上书写代码，笔者将给出使用递归和不使用递归的两种解答：
不使用递归的情况
（注：LeetCode平台给出了节点类，为了调试方便，在自己的IDE上相应创建相同的节点类。）
不使用递归就要考虑链表如何构建，这里先给出不带虚拟头结点的链表解决方案（也就是头结点储存了我们的数据）：

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while(head != null && head.val == val){
            ListNode delNode = head;
            head = head.next;
            delNode.next = null;
        }
        if(head == null)
            return head;//链表里全是要删除的元素则返回null
        ListNode prev = head;
        while(prev.next != null){
            if(prev.next.val == val){
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }
            else
                prev = prev.next;
        }
        return head;
    }
}

带虚拟头结点的解决方案：

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //设置虚拟头结点，不过对用户是屏蔽的
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        ListNode prev = dummyHead;
        while(prev.next != null){
            if(prev.next.val == val){
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }
            else
                prev = prev.next;
        }
        return dummyHead.next;
    }
}

设置了虚拟头结点后可以省去第一步对真实储存了信息的头结点的判断，减少一点代码量。
使用递归方案
使用递归方案就要思考递归的逻辑是什么

• 链表头结点为空否，为空则返回(递归终止条件)
• 递归处理去掉头结点后的链表(递归过程)
• 头结点是否需要删除，如果是则返回头结点后的链表，否则返回头结点(最后处理)

依照这个逻辑给出下面用递归方式书写的代码:

public class Solution4 {
    public ListNode remove(ListNode head,int val){
        if(head == null)
            return head;
        head.next = remove(head.next,val);
        return head.val == val ? head.next : head;
    }
}

可以看到，使用递归后，我们的代码简化到只有4行。

尽管递归能很大程度上简化代码，不过使用递归是有代价的，递归需要使用系统栈，每次调用要将断点保存到系统栈中，如果调用过程很多，将非常消耗系统资源，所以性能上一般比不用递归的方式差一些。不过一些复杂的数据结构中(树、森林、图等)，递归能很好地展示程序逻辑，所以有时为了减少代码量增加程序可读性，使用递归是必要的。

---

二分搜索树

树结构同样具有天然的递归性质，这里以二分搜索树的各种操作为例，来看一下递归的用处，二分搜索树的所有相关操作都用递归的方式实现:

import java.util.Stack;
public class BST<E extends Comparable<E>> {
    //二分搜索树并不支持所有泛型，泛型必须满足可比较性
    private class Node{
        //二分搜索树作为内部私有类，节点对用户是屏蔽的,用户不必知道节点如何
        public E e;
        public Node left,right;
        public Node(E e){
            this.e = e;
            left = null;
            right = null;
        }
    }
    private Node root;
    private int size;

    public BST(){
        //不写的话也是可以，因为这里的构造函数和默认一样
        root = null;
        size = 0;
    }
    public int size(){
        return size;
    }
    public boolean isEmpty(){
        return size == 0;
    }
    public void add(E e){
        root = add(root,e);
    }
    private Node add(Node node, E e){
        //向以Node为根的二分搜索树插入元素e，递归
        //返回插入新节点后二分搜索树的根
        if(node == null){
            size ++;
            return new Node(e);
        }
        //以上是递归终止条件,下是递归调用
        if(e.compareTo(node.e)<0)
            node.left = add(node.left,e);
        else if(e.compareTo(node.e)>0)
            node.right = add(node.right,e);
        return node;
    }
    //二分搜索树查询操作
    public boolean contains(E e){
        return contains(root,e);
    }
    private boolean contains(Node node,E e){
        if(node == null)
            return false;
        if(e.compareTo(node.e) == 0)
            return true;
        else if (e.compareTo(node.e)<0)
            return contains(node.left,e);
        else
            return contains(node.right,e);
    }
    //二分搜索树的遍历操作
    public void preOrder(){
        preOrder(root);
    }
    private void preOrder(Node node){
        //前序遍历以node为根的二分搜索树，递归算法
        //if(node == null) return ;//递归终止条件
        if(node != null) {
            System.out.println(node.e);
            preOrder(node.left);
            preOrder(node.right);
        }
    }
    //前序遍历的非递归实现
    public void preOrderNR(){
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.println(cur.e);
            if(cur.right != null)
                stack.push(cur.right);
            if(cur.left != null)
                stack.push(cur.left);
        }
    }
    //中序遍历
    public void inOrder(){
        inOrder(root);
    }
    private void inOrder(Node node){
        if(node == null)
            return ;
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }
    //后序遍历
    public void postOrder(){
        postOrder(root);
    }
    private void postOrder(Node node){
        if(node == null)
            return ;
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        generateBSTString(root, 0, res);
        return res.toString();
    }
    //生成以node为根节点，深度为depth的描述二叉树的字符串
    private void generateBSTString(Node node,int depth,StringBuilder res){
        if(node==null){
            res.append(generateDepthString(depth) + "null\n");
            return;
        }
        res.append(generateDepthString(depth) + node.e + "\n");
        generateBSTString(node.left,depth+1,res);
        generateBSTString(node.right,depth+1,res);
    }
    private String generateDepthString(int depth){
        StringBuilder res = new StringBuilder();
        for(int i=0;i<depth;i++)
            res.append("--");
        return res.toString();
    }
}

从代码中看到，其中的前序遍历过程我也给出了非递归方式的写法，非递归的写法需要借助栈这种数据结构，代码相应也复杂的多。可见递归方式能带来很大的便利。

---

递归的用处远比想象的要多，熟练运用递归能让我们写出很有feel的代码。