Need Clarification on Recursive Function Methodology

user_18500990 0
Viewed 61

Apologies in advance, I am very new to c and programming.

I'm currently working on understanding how recursive functions work and have a major mental block.

I was provided an example of a recursive function that creates a "pyramid" of sorts out of hash symbols (see below). I can't understand why the output is not flipped horizontally, with n hashes on top and 1 hash on bottom.

In trying to make sense of it, I created a table with the number of loops, n value, n - 1 value, and how man hashes I think it should print.

enter image description here

On loop 1, n starts out as 4 and the "for loop" should run 4 times since "i" goes through during 0, 1, 2, and 3.
Line break
On loop 2, n is now 3 and the "for loop" should run 3 times since "i" goes through during 0, 1, and 2.
And so on and so forth...

I created nested for loops that I thought would provide the same result: n (height) is 4 originally and works down to 0, i works upwards from 0 printing hashes but the result is the exact opposite.

#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");
}

Result below. Their result on top. Mine below it.

enter image description here

If someone could please help clarify what I'm missing I would greatly appreciate it.

cs50 c
2 Answers

Look to see when this recursion will emit its first out put

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

    draw(n - 1);

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

printf("\n");
}

see that it keeps calling itself before the printf, it only stops doing that one n reaches 0, then it starts returning and calling the prints, but in reverse order of n.

ie it goes

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

You have called the draw(n-1); before the for loop. Therefore the function recursively called like this.

First Draw(4); function calls from main function. Then calls Draw(4-1); -> Draw(3); Then again Draw(3-1); -> Draw(2); it doesn’t go to the line which has for loop until base condition. So, next again calls Draw(2-1); -> Draw(1); After that Draw(1-1); -> Draw(0); since n=0 function will return.

Next go backwards now. Because you haven’t completed the Draw(n) function. You only did recursively calling it self. After finishing that you have printing part. Since you are now in Draw(1), you starts printing from 1. You came to Draw(1) from Draw(4). So now you have to go again back to Draw(4) from Draw(1). That’s why we go backwards.

Path explanation:

Now you are in Draw(1); so it prints #. Then finishes Draw(1); next Draw(2); so it prints ##. next Draw(3); so it prints ###. next Draw(4); so it prints #### .

That’s how the recursion function works. Therefore the output is,

#
##
###
####

In your nested loop it starts from 4. Because you have used n=height. So your code should start from n=1 like below code.

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