目录

递归

• 本质上将原来的问题，转换为一个更小的同样的问题。

  
  

数组的求和其实用不到递归，这是只是为了演示。求解最基本的问题是很简单的，需要我们写逻辑代码来求解，而不能直接返回值的。其实最基本的问题就是递归函数的出口。

链表天然的递归性

删除链表中所有的值为v的节点

/**
 * @parm head : 链表的头结点
 * @parm val ： 要删除节点的值
 */
public ListNode removeElements(ListNode head, int val) {

    if(head == null){
        return null;
    }
    ListNode res = removeElements(head.next, val);
    if(head.val == val){
        return res;
    }else{
        head.next = res;
        return head;
    }

}

上面的代码可以简化为：

/**
 * @parm head : 链表的头结点
 * @parm val ： 要删除节点的值
 */
public ListNode removeElements(ListNode head, int val) {

    if(head == null){
        return null;
    }
    head.next = removeElements(head.next, val);
    return head.val == val ? head.next : head;

}

递归的“微观”解读

数组求和

函数本身就是实现一个功能。在递归函数中，可以看成是调用一个功能函数，或者是其他的函数，只是方法名相同而已，这样还好理解一点。递归函数在每次递归调用的时候，虽然是同一个方法，但是此时的参数值已经变了。

删除链表中所有值为val的节点

图中红色的1,2,3，对应着代码中的1,2,3步操作。第一次调用时第二部的head.next的值要依赖第二次调用的返回值，一次类推。

从代码中并没有看到真正删除节点的操作，删除节点的操作其实是在返回过程删除的，head.next指向一个链表。

如果递归的次数大多，就会导致栈内存溢出。

关注微信公众号获取更多相关资源

Android行动派