Рекурсивная функция

Question

Учитывая следующую рекурсивную функцию, что будет напечатано mysterious (4)?

void mysterious(int x) {
    if (x == 0) return;
    printf(“%d ”, x);
    mysterious(x-1);
    mysterious(x-1);
}

Вот мой стек вызовов:

mysterious(4) => print 4
mysterious(3) => print 3
mysterious(2) => print 2
mysterious(1) => print 1
mysterious(0) => print 0

Это правильно?

Answer 1

Поскольку каждый вызов функции выполняет 2 вызова функции по очереди, вы можете визуализировать свою рекурсию, так сказать, в виде «дерева», и вы выполняете обход предзаказа по дереву.

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

                           4
                           |
                3----------+----------3
                |                     |
           2----+----2           2----+----2
           |         |           |         |
        1--+--1   1--+--1     1--+--1   1--+--1

Порядок выполнения, который у вас есть:

• печать числа
• вызов функции с x-1
• вызовите функцию снова с x-1

Это будет соответствовать нашей "визуализации дерева", выполнив:

• выведите корень
• пересекителевый узел
• пересекает правый узел

Вывод будет:

    4 3 2 1 1 2 1 1 3 2 1 1 2 1 1

Answer 2

Почему бы вам просто не ввести его в редактор на выбранном вами языке, скомпилировать и запустить?Я выбрал Java, но это только потому, что я сейчас нахожусь между установками CygWin на моем компьютере - я бы предпочел использовать C: -)

public class testprog {
    public static void mysterious(int x) {
        if (x == 0) return;
        System.out.print(x + " ");
        mysterious(x-1);
        mysterious(x-1);
    }
    public static void main(String args[]) {
        mysterious(4);
    }
}

Это выдает числа:

4 3 2 1 1 2 1 1 3 2 1 1 2 1 1

По сути, происходит то, что на каждом уровне вы распечатываете номер, затем дважды вызываете следующий уровень со следующим наименьшим номером (если он не достиг нуля).

В сторону: технически, вы do вызываете следующий слой с нулем, но, поскольку он сразу возвращается, это не влияет на вывод.

Надеемся, что следующая диаграмма проиллюстрирует это лучше, сразные символы, представляющие разные слои:

(4) (-------------------------------) (-------------------------------)
     {3} {-----------} {-----------}   {3} {-----------} {-----------}
          [2] [1] [1]   [2] [1] [1]         [2] [1] [1]   [2] [1] [1]

Answer 3

Нет, это будет

mysterious(4) => print 4
mysterious(3) => print 3
mysterious(2) => print 2
mysterious(1) => print 1
mysterious(1) => print 1
mysterious(2) => print 2
mysterious(1) => print 1
mysterious(1) => print 1
mysterious(3) => print 3
mysterious(2) => print 2
mysterious(1) => print 1
mysterious(1) => print 1
mysterious(2) => print 2
mysterious(1) => print 1
mysterious(1) => print 1

, потому что 0 приведет к более раннему возврату функции из-за этого двойного вызова.

Answer 4

Нет.Он не будет печатать 0, потому что при x==0 он вернется

Также, поскольку у вас есть

mysterious(x-1);
mysterious(x-1);

, он напечатает (исправлено)

4 3 2 1 1 2 1 1 3 2 1 1 2 1 1

mysterious(x-1); не меняет значение x.он просто снова вызывает mysterious(), на этот раз со значением x-1