Проблема с рекурсией – я не понимаю, почему вывод получается обратным

Я в настоящее время изучаю рекурсию в Java. Я сделал небольшой код для практики.

public class Tester{
    public static void main(String[] args){
        rec(5);
    }
    public static void rec(int x){
        if(x<=0){
            return;
        }else{
            System.out.print(x+" ");
            rec(x-1);
        }
    }
}
// Вывод: 5 4 3 2 1 

Но если я сейчас поменяю System.out.print(x+" "); с rec(x-1);, я получу совершенно другой вывод, а именно обратный: 1 2 3 4 5

Как это может быть возможно? Я понимаю это так:

У нас есть целое число 5, и мы проходим через метод. Условие if не применяется, поэтому мы уменьшаем 5 на 1, и у нас x=4, мы повторяем метод (печать не достигнута, и таким образом ничего не печатается). Как уже сказано, мы делаем то же самое с x=4. Условие if не применяется, мы уменьшаем 4 на 1 и повторяем метод. Мы повторяем, пока не получим x=0. В этом случае мы возвращаемся, так что это конец метода. Я совсем не понимаю, как мы получили обратный вывод, я даже не понимаю, почему у нас есть вывод…? :s

Попробуйте это:

public class Tester{
    public static void main(String[] args){
        rec(5);
    }
    public static void rec(int x){
        if(x<=0){
            return;
        }else{
            rec(x-1);
            System.out.print(x+" ");
        }
    }
}

Причина в том, что сначала вам нужно достичь условия выхода (x==0), а затем начать печатать числа в обратном порядке относительно вызова вашего метода:

rec(5)
    rec(4)
        rec(3)
            rec(2)
                rec(1)
                    rec(0) // Мы останавливаемся здесь
                System.out.print('1 ')
            System.out.print('2 ')
        System.out.print('3 ')
    System.out.print('4 ')
System.out.print('5 ')

Хорошо, давайте изучим первый случай.

Сначала оператор печати, а затем рекурсивный вызов:
Сухой запуск:

x = 5  Печатает 5, затем вызывает rec(4)
x = 4  Печатает 4, затем вызывает rec(3)
x = 3  Печатает 3, затем вызывает rec(2)
x = 2  Печатает 2, затем вызывает rec(1)
x = 1  Печатает 1, затем вызывает rec(0)
x = 0  Достигнуто базовое условие, поэтому метод возвращается в следующей последовательности->
rec(1) -> rec(2) -> rec(3) -> rec(4) -> rec(5) ->main()

Поскольку в этом случае не было больше операторов для выполнения после рекурсивного вызова, ничего не произошло, и метод начал возвращаться назад. Теперь для второго случая:
Сначала рекурсивный вызов, затем оператор печати.
Сухой запуск:

x = 5 так как x не меньше или равно 0, идет к rec(4), но оператор печати ждет своего выполнения. Это не произойдет, пока рекурсивный вызов не вернется.
x = 4 так как x не меньше или равно 0, идет к rec(3), но снова печать на удержании.
x = 3 так как x не меньше или равно 0, идет к rec(2), но все еще печать на удержании.
x = 2 так как x не меньше или равно 0, идет к rec(1), но все еще печать на удержании.
x = 1 так как x не меньше или равно 0, идет к rec(0), но все еще печать на удержании.
x = 0 так как x теперь 0, rec(0) возвращается к rec(1).

Теперь у rec(1) есть ожидающий оператор печати, который сейчас выполняется со значением 1.
затем у rec(2) был ожидающий оператор печати, который сейчас выполняется со значением 2.
затем у rec(3) был ожидающий оператор печати, который сейчас выполняется со значением 3.
затем у rec(4) был ожидающий оператор печати, который сейчас выполняется со значением 4.
затем у rec(5) был ожидающий оператор печати, который сейчас выполняется со значением 5.
и затем rec(5) возвращается к main().

Таким образом, в этом случае вывод: 1->2->3->4->5, а в первом случае это было 5->4->3->2->1.

Надеюсь, это поможет вам понять 🙂

Получаемые вами выводы верны.

В первом случае:

...
System.out.print(x+" ");
rec(x-1);
...

Правильный вывод: 5 4 3 2 1

А во втором случае:

...
rec(x-1);
System.out.print(x+" ");
...

Правильный вывод: 1 2 3 4 5

Объяснение:
В рекурсивной функции каждый вызов помещается в стек (поэтому выполняется в порядке последний пришел – первый вышел).

В первом случае rec(x) сначала печатает значение своего аргумента, а затем вызывает rec(x-1), следовательно, порядок оказывается x x-1 x-2 .... Следующей будет последовательность выполнения:

rec(5)
    печатает 5
    rec(4)
        печатает 4
        rec(3)
            печатает 3
            rec(2)
                печатает 2
                rec(1)
                    печатает 1
                    rec(0)
                        rec(0) возвращается
                    rec(1) возвращается
                rec(2) возвращается
            rec(3) возвращается
         rec(4) возвращается
     rec(5) возвращается

Во втором случае функция rec(x) сначала вызывает rec(x-1) до того, как напечатает свой аргумент. Вот последовательность выполнения во втором случае:

rec(5)
    rec(4)
        rec(3)
            rec(2)
                rec(1)
                    rec(0)
                        rec(0) возвращается
                    печать 1
                    rec(1) возвращается
                печать 2
                rec(2) возвращается
            печать 3
            rec(3) возвращается
         печать 4
         rec(4) возвращается
     печать 5
     rec(5) возвращается

Надеюсь, это поможет вам понять выводы, которые вы получаете в вышеупомянутых двух случаях. Я также призываю вас прочитать следующие ответы на stackoverflow здесь, которые описывают, как работают рекурсивные функции более подробно.