递归函数

发布于 2024-10-08 05:27:29 字数 368 浏览 1 评论 0原文

给定以下递归函数，神秘（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

这是正确的吗？

原文

Given the following recursive function, what would be printed by mysterious(4)?

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

Here is my call stack:

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

Is this correct?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

余生再见 2024-10-15 05:27:29

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

Because every function call makes 2 function calls in turn, you can visualize your recursion as a "tree" so to speak, and you are doing a preorder traversal on the tree.

It would look something like this:

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

The order of execution that you have is:

print the number
call the function with x-1
call the function with x-1 again

This would correspond to our "tree visualization" by doing:

print the root
traverse the left node
traverse the right node

The output would be:

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

回复收藏 0 原文

沐歌 2024-10-15 05:27:29

为什么不直接用您选择的语言将其输入到编辑器中，编译并运行呢？我选择了 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]

Why don't you just type it in to an editor in your language of choice, compile it and run? I chose Java but that's just because I'm between CygWin installs on my box at the moment - I'd much rather be using 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);
    }
}

This outputs the numbers:

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

Basically, what's happening is that, at each level, you print out the number then call the next level twice with the next lowest number (unless it's reached zero).

Aside: technically, you do call the next layer with zero but, since it returns straight away, it has no affect on the output.

The following diagram will hopefully illustrate this better, with different symbols representing different layers:

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

回复收藏 0 原文

饮湿 2024-10-15 05:27:29

不，这是

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 会导致函数提前返回，并且由于两次调用。

No, it will be

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

because 0 will cause the function to return earlier and because of that double-call.

回复收藏 0 原文