递归函数

Question

鉴于以下递归函数,神秘(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

基本上,正在发生的事情是,在每个级别,您打印出数字然后用下一个最低数字调用下一个级别(除非它达到零).

除此之外:从技术上讲,你确实用零调用下一层,但由于它直接返回,它对输出没有影响.

下图将有望更好地说明这一点,不同的符号代表不同的层:

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