Java递归算法(Java算法和数据结构总结笔记)[6/20]

1、递归是什么

递归是什么，简单的说递归就是循环调用。

递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

解决的问题：

• 数据的定义是按递归定义的。
• 问题解法按递归算法实现。
• 数据的结构形式是按递归定义的。如二叉树、广义表等

2、递归算法的使用

（1）使用的递归求和

    /**
     * 使用递归求和
     * @param arr 集合
     * @return 返回的和
     */
    public static int sum(int[] arr){
        return sum(arr,0);
    }
 
    public static int sum(int[] arr, int index){
        // 判断是否是最后一个元素
        if (index == arr.length){
            return 0;
        }
        // 递归求值
        return arr[index] + sum(arr, index + 1);
    }

（2）解析递归的调用过程

1、sum() 方法递归调用，拿到最后一个值后，开始返回，并累加值，即 sum(arr, 2)返回值为0， 

sum(arr, 1)返回值为0+10，以此累加求和。

3、使用递归删除链表中的值

（1）创建 ListNode 类

/**
 * @version 1.0
 * @description: TODO 链表
 */
public class ListNode {
 
    public int val;
    public ListNode next;
 
    public ListNode(int val){
        this.val = val;
    }
 
    // 把数组中的值转换成链表的形式
    public ListNode(int[] arr) {
        if (arr == null || arr.length == 0){
            throw new IllegalArgumentException("集合不能为空");
        }
 
        this.val = arr[0];
        ListNode cur = this;
        for (int i = 1; i < arr.length; i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
    }
 
    @Override
    public String toString() {
 
        StringBuilder res = new StringBuilder();
        res.append("head [ ");
 
        ListNode cur = this;
        while (cur != null){
            res.append(cur.val + "->");
            cur = cur.next;
        }
        res.append("NULL ]");
 
        return res.toString();
    }
}

（2）使用递归的方式删除链表中的一个节点

    /**
     * 使用递归的方法删除节点
     * @param head 头节点
     * @param val 值
     * @return 返回值
     */
    public ListNode removeElementByRecursion(ListNode head, int val){
 
        if (head == null){
            return null;
        }
        head.next = removeElementByRecursion(head.next, val);
        return head.val == val ? head.next : head;
 
    }

如果不使用递归：

    /**
     * 使用while循环的方法删除节点
     * @param head 头节点
     * @param val 值
     * @return 返回值
     */
    public ListNode removeElement(ListNode head, int val){
 
        // 创建一个虚拟头节点，方便后续遍历
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
 
        // 从虚拟节点开始遍历
        ListNode prev = dummyHead;
 
        // 判断虚拟头节点的下一个节点的值是否为空
        while (prev.next != null){
 
            // 如果节点的值等于要删除的值，则把下下个节点的值的指向赋给当前
            if (prev.next.val == val){
                prev.next = prev.next.next;
            }else {
                // 继续下一个值的遍历
                prev = prev.next;
            }
        }
 
        // 返回虚拟头节点的下一个值，即实际的值
        return dummyHead.next;
    }

由此可见，使用递归的方式删除节点，代码会简洁很多。

4、打印输出递归的调用过程

    /**
     * 打印递归的调用详情
     * @param head 头节点
     * @param val 值
     * @param depth 深度
     * @return 返回值
     */
    public ListNode removeElementByRecursionInfo(ListNode head, int val, int depth){
 
        String depthStr = generateDepthStr(depth);
 
        System.out.print(depthStr);
        System.out.println("调用了【remove】方法,删除:" + val + "在:" + head + "中!");
 
        if (head == null){
            System.out.print(depthStr);
            System.out.println("Return:" + head);
            return head;
        }
        ListNode res = removeElementByRecursionInfo(head.next, val, depth + 1);
 
        System.out.print(depthStr);
        System.out.println("执行后【remove】方法,删除:" + val + "现在:" + res);
 
        ListNode ret;
        if (head.val == val){
            ret = res;
        }else {
            head.next = res;
            ret = head;
        }
        System.out.print(depthStr);
        System.out.println("现在返回的值是:" + ret);
        return ret;
    }
 
    private String generateDepthStr(int depth) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            builder.append("--");
        }
        return builder.toString();
    }

打印详情：