递归函数

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

你为什么不直接用你选择的语言编辑一个编辑器，编译它并运行？我选择了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] 

Answer 2

号将不打印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

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

因为每个函数调用都会依次产生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