问问同学们，递归问题如何解决

Question

从尾到头打印链表

package com;

import java.util.ArrayList;

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}


public class Solution {
    //递归函数
    public static void recursion(ListNode head, ArrayList<Integer> res) {
        if (head != null) {
            //先往链表深处遍历
            recursion(head.next, res);
            //再填充到数组就是逆序
            res.add(head.val);

        }

    }

    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        //递归函数解决
        recursion(listNode, res);
        return res;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        ArrayList<Integer> integers = printListFromTailToHead(listNode1);
        System.out.println(integers);


    }
}

问题:为什么在遇到终止条件head==null之后，仍弄够返回recursion中的res.add(head.var)处执行，且还能循环执行四次。

Answer 1

该回答引用ChatGPT
在这段代码中，递归函数recursion()在链表未到达末尾时一直向下递归，然后从最后一个节点开始逆序遍历链表，并将节点的值加入到ArrayList中，这样最终返回的ArrayList中就是链表逆序的值。

当遇到终止条件head == null时，程序不会立即返回，而是逐层返回到上一级递归。这是因为在递归中，每次调用recursion()函数时，都会将当前的函数压入函数调用栈中，并等待下一层递归函数返回后继续执行。当最后一个递归函数执行完毕后，它会将结果返回到上一层递归函数，上一层递归函数再将结果返回到更上一层递归函数，以此类推，直到返回到最初的调用点。因此，当遇到终止条件时，程序不会立即返回，而是等待下一层递归函数执行完毕后再继续执行。

在这段代码中，当链表遍历到最后一个节点时，最后一个节点会被先加入到ArrayList中，然后返回到上一层递归函数，依次将上一层的节点加入到ArrayList中，直到返回到最初的调用点，此时ArrayList中的节点就是链表的逆序值。因此，程序会在终止条件head == null处返回，但是会继续执行后面的res.add(head.val)语句，将最后一个节点的值加入到ArrayList中，然后返回到上一层递归函数，继续执行上一层递归函数的res.add(head.val)语句，以此类推，直到返回到最初的调用点，此时ArrayList中包含了整个链表的逆序值。

总之，在递归函数recursion()中，即使遇到终止条件head == null时，程序仍然会等待下一层递归函数执行完毕后再返回，直到返回到最初的调用点。