需要澄清递归函数方法论

Question

提前致歉，我对 c 和编程还很陌生。

我目前正在努力理解递归函数的工作原理并且有一个主要的心理障碍。

有人向我提供了一个递归函数示例，该函数创建了各种散列符号的“金字塔”（见下文）。我不明白为什么输出没有水平翻转，顶部有 n 个哈希，底部有 1 个哈希。

为了理解它，我创建了一个 table，其中包含循环次数、n 值、n - 1 值，以及我认为它应该打印的 man 哈希值。

在循环 1 中，n 开始时为 4，并且“for 循环”应该运行 4 次，因为“i”在 0、1、2 和 3 期间经过。
越线
在循环 2 中，n 现在是 3，并且“for 循环”应该运行 3 次，因为“i”在 0、1 和 2 期间经过。
等等……

我创建了嵌套的 for 循环，我认为它会提供相同的结果：n（高度）最初是 4，然后向下工作到 0，我从 0 向上打印哈希，但结果恰恰相反。

#include <cs50.h>
#include <stdio.h>

void draw(int n);

int main(void)
{
    // prompt user for height of pyramid
    int height = get_int("Height ");

    // call recursive 'draw' function
    draw(height);

    printf("\n");

    // my nested loop function I made that I can't tell how is different from the recursive function
    for (int n = height; n >= 0; n--)
    {
        for (int i = 0; i < n; i++)
        {
            printf("#");
        }
        printf("\n");
    }
}

// recursive function example I was given that I cannot make sense of
void draw(int n)
{
    if (n <= 0)
    {
        return;
    }

    draw(n - 1);

    for (int i = 0; i < n; i++)
    {
            printf("#");
    }

printf("\n");
}

结果如下。他们的成绩名列前茅。我的在它下面。

如果有人可以帮助澄清我遗漏的内容，我将不胜感激。

Answer 1

查看此递归何时会发出第一个输出

void draw(int n)
{
    if (n <= 0)
    {
        return;
    }

    draw(n - 1);

    for (int i = 0; i < n; i++)
    {
            printf("#");
    }

printf("\n");
}

看到它在 printf 之前一直调用自己，它只是在 n 达到 0 时停止，然后它开始返回并调用打印，但是在n.

的倒序

就是这样

 draw(4)->draw(3)->draw(2)->draw(1)->draw(0)
                            printf loop *1
                   printf loop * 2
          printf loop * 3
 printf loop * 4

Answer 2

您在 for 循环之前调用了 draw(n-1);。因此函数递归调用是这样的。

第一个 Draw(4); 函数从 main 函数调用。然后调用 Draw(4-1); -> Draw(3); 然后再次调用 Draw(3-1); -> Draw(2); 它不会转到有 for 循环的行，直到基本条件。因此，接下来再次调用 Draw(2-1); -> Draw(1); 之后 Draw(1-1); -> Draw(0); 因为 n=0 函数将 return.

接下来现在倒退。因为你还没有完成 Draw(n) 函数。你只是递归地调用它自己。完成后你有打印部分。由于您现在处于 Draw(1)，因此您从 1 开始打印。您从 Draw(4) 来到 Draw(1)。所以现在你必须再次从 Draw(1) 回到 Draw(4)。这就是我们倒退的原因。

路径说明：

现在你在抽奖(1);所以它打印 #。然后完成 Draw(1)； next Draw(2); 所以它打印 ##。 next Draw(3); 所以它打印 ###。 next Draw(4); 所以它打印 #### .

这就是递归函数的工作原理。因此输出是，

#
##
###
####

在您的嵌套循环中，它从 4 开始。因为您使用了 n=height。所以你的代码应该像下面的代码一样从 n=1 开始。

for (int n = 1; n <= height ; n++)
{
    for (int i = 0; i < n; i++)
    {
        printf("#");
    }
    printf("\n");
}

需要澄清递归函数方法论

Need Clarification on Recursive Function Methodology

c

cs50