простой рекурсивный пример - пожалуйста, помогите мне понять рекурсию

Question

    public static int triple(int n)
    {
        if (n == 0)
            return 0;
        else
            total = 3 + triple(n-1);
    System.out.println(total);
    return total;
    }

Хорошо, у меня есть этот простой пример повторения, который я, кажется, просто не могу понять, я надеялся, что кто-то будет достаточно любезен, чтобы пройти меня по циклам за тем, как программа получает свой вывод.

Вот то, что я думал, произойдет.Допустим, n=5 Итак, программа циклически повторяет и нажимает total = 3 + triple(5-1), что, я думаю, будет равно 7 ... что неправильно, программа печатает

3
6
9
12
15

Итак ... потом я подумал, что триплет должен пробежать снова, прежде чем печатать итоговое значение ... что я верю, но я простотогда я вообще не понимаю, как все это получается.

Потому что это будет выглядеть так:

3 + triple(4)
       3 + triple(3)
               3 + triple(2)
                       3 + triple(1)
                                =3

Может кто-нибудь объяснить, пожалуйста, как вы можете, я очень потерян!

Answer 1

Вы интерпретируете это немного неправильно.Это выглядит примерно так:

triple(5) = 3 + triple(4)
triple(4) = 3 + triple(3)
triple(3) = 3 + triple(2)
triple(2) = 3 + triple(1)
triple(1) = 3 + triple(0)
triple(0) = 0

Теперь представьте, что triple(0), triple(1) и т. Д. - все это отдельные переменные, и решите для triple(5), пробираясь вверх.

Answer 2

Ваш вывод должен быть прочитан следующим образом:

3 = triple(1) = 3+triple(0)
6 = triple(2) = 3+triple(1)
9 = triple(3) = 3+triple(2)
12 = triple(4) = 3+triple(3)
15 = triple(5) = 3+triple(4)

Это потому, что triple (n) вызовет triple (n-1) до распечатки сообщения.Таким образом, ваше тройное (5) сообщение будет напечатано последним.

Answer 3

Так что не получится ли это сделать до нуля (вычитая 1), а затем добавить 3 к каждому (0 3 6 и т. Д.).

Это вывод, который я получаю:

n:5
n:4
n:3
n:2
n:1
n:0
total:3
total:6
total:9
total:12
total:15

То, что он делает, это вычитает одно из n каждого перечисления, а затем добавляет 3 к 0-5

.

Answer 4

triple(0) = 0
triple(1) = 3 + triple(0) i.e. 3+0=3
triple(2) = 3 + triple(1) i.e. 3+3=6
triple(3) = 3 + triple(2) i.e. 3+6=9
triple(4) = 3 + triple(3) i.e. 3+9=12
triple(5) = 3 + triple(4) i.e. 3+12=15

Answer 5

public static int triple(int n)
{

if (n == 0)
return 0;
else
return 3 + triple(n-1);
System.out.println(return);
}

Не обращайте внимания на println (возвращайте) его только для целей понимания. Вот как я разбил его, чтобы наконец получить хорошее представление о рекурсивных функциях / методах.

triple(3)
return 3 + triple(3-1)_is_6<---- (return = 9)<--
println(return)

    triple(2)
    return 3 + triple(2-1)_is_3<-- (return = 6)<----
    println(return);

              triple(1)
              return 3 + triple(1-1)_is_0<---- (return = 3)<--
              println(return)

                       triple(0)
                       return 0; is 0 (return = 0)<----
                       (no println for n==0)

Спасибо всем за помощь в понимании этого. Чего я не делал, так это помнил, что каждая тройка (n-1) возвращает свое собственное значение, которое затем вычисляется в вызове над ним.

СПАСИБО СНОВА!

Answer 6

Когда выполнение достигает этой точки, тройной метод начинает выполняться снова с самого начала.Как только он вернется, выполнение возобновится на следующей строке.Это происходит рекурсивно .

Таким образом, порядок выполнения выглядит примерно так:

1. if (n == 0) // n == 5 на этом этапе, условие ложно
2. total = 3 + triple (n-1) // мы должны вычислить triple (4)
3. , если (n == 0) // n == 4 сейчас.
4. total = 3 + triple (n-1) // мы должны вычислить triple (3)
5. ... и т. Д., Пока n не будет == 0:
6. , если(n == 0) // true!
7. return 0 // возвращает 0
8. total = 3 + 0 // 0 происходит от triple (n-1), который только что возвратил 0
9. System.out.println (всего);// печатает 3
10. return total;// возвращает 3
11. total = 3 + 3;// снова 3 происходит из тройного (n-1), где n == 2
12. System.out.println (total);// на этот раз печатает 6
13. ... и т. д.

Обратите внимание, что функция, как определено, просто умножает вход на 3 и печатает результат на каждом кратном.