将原来的问题,转化为更小的同一问题

public class Sum {    public static int sum(int[] arr){        return sum(arr,0);    }    //计算arr[l...n]这个区间内所有数字的和    private static int sum(int[] arr,int l){        //求解最基本的问题        if(l == arr.length)            return 0;        //把原问题转化为更小的问题        return arr[l] + sum(arr,l + 1);    }    public static void main(String[] args) {        int[] nums = {
   1, 2, 3, 4, 5, 6, 7, 8};        System.out.println(sum(nums)); //36    }}

1.链表的天然递归结构性质

解决链表中删除元素的问题

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution3 {    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;    }    public static void main(String[] args) {        int[] nums = {
   1, 2, 6, 3, 4, 5, 6};        ListNode head = new ListNode(nums);        System.out.println(head);  //1->2->6->3->4->5->6->NULL        ListNode res = (new Solution()).removeElements(head , 6);        System.out.println(res);   //1->2->3->4->5->NULL    }}

2.递归运行的机制

 

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution4 {    public ListNode removeElements(ListNode head, int val,int depth) {        String depthString = generateDepthString(depth);        System.out.print(depthString);        System.out.println("Call: remove " + val +" "+ head);        if(head == null){            System.out.print(depthString);            System.out.println("Return " + head);            return null;        }        ListNode res = removeElements(head.next,val,depth + 1);        System.out.print(depthString);        System.out.println("After remove " + val + ": " + res);        ListNode ret;        if(head.val == val)            ret = res;        else{            head.next = res;            ret = head;        }        System.out.print(depthString);        System.out.println("Return: " + ret);        return ret;    }    private String generateDepthString(int depth){        StringBuilder res = new StringBuilder();        for(int i = 0;i < depth;i ++){            res.append("--");        }        return res.toString();    }    public static void main(String[] args) {        int[] nums = {
   1, 2, 6, 3, 4, 5, 6};        ListNode head = new ListNode(nums);        System.out.println(head);        ListNode res = (new Solution4()).removeElements(head , 6,0);        System.out.println(res);//        1->2->6->3->4->5->6->NULL//        Call: remove 6 1->2->6->3->4->5->6->NULL//                --Call: remove 6 2->6->3->4->5->6->NULL//                ----Call: remove 6 6->3->4->5->6->NULL//                ------Call: remove 6 3->4->5->6->NULL//                --------Call: remove 6 4->5->6->NULL//                ----------Call: remove 6 5->6->NULL//                ------------Call: remove 6 6->NULL//                --------------Call: remove 6 null//                --------------Return null//                ------------After remove 6: null//                ------------Return: null//                ----------After remove 6: null//                ----------Return: 5->NULL//                --------After remove 6: 5->NULL//                --------Return: 4->5->NULL//                ------After remove 6: 4->5->NULL//                ------Return: 3->4->5->NULL//                ----After remove 6: 3->4->5->NULL//                ----Return: 3->4->5->NULL//                --After remove 6: 3->4->5->NULL//                --Return: 2->3->4->5->NULL//        After remove 6: 2->3->4->5->NULL//        Return: 1->2->3->4->5->NULL//        1->2->3->4->5->NULL    }}