I used the debugger to examine this code but not understanding a couple areas.

  1. Why does the for loop repeat after it exits to print a new line? If it exits the loop, shouldn’t it be done with it?
  2. Why is n incremented and not i as stated with i++?

int main(void)
{
    int height = get_int("Height: ");

    draw(height);
}

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

    draw(n - 1);

    for (int i = 0; i < n; i++)
    {
        printf("#");
    }
    printf("\n");
}
  • FareshEnglish
    1·
    10 months ago

    I think it’s wrong to look at recursion that way. What you just showed is how to translate a recursive solution to an iterative one, which only makes recursion look like an inferior version of a loop. With recursion the idea is that you solve the problem for trivial/base cases (eg. we know that the first and second numbers of the Fibonacci sequence are both 1), then you assume a smaller problem has already been solved (eg. we already know what fibonacci(n-2) and fibonacci(n-1) is) and now you program the solution for the next step (fibonacci(n)).

    In this case the problem we want to solve is drawing a triangle of a specific height with a base of the same width. The base case is the empty or negative-height triangle. In this case we draw nothing. Now we assume we already know how to draw a triangle of height height - 1. The question we ask ourselves now is how do we draw the triangle of height height when we already have a solution for the problem of how to draw a triangle of height - 1. We see that the triangle of height height is simply the triangle of height height - 1 with another row of the same length as the height of the triangle added to the end. So what we do is we draw the triangle of height - 1 (which is done by using the same solution we are writing right now, but we shouldn’t meditate about what that entails when writing, since it’s just going to unnecessarily cause us headaches), and then draw a row of length height at the end. Now we have a solution for the base case (other problems such as the fibonacci function I mentioned can have more than one base case), and a solution for all the other cases written with the assumption that a previous problem has already been solved. This is how one is supposed to write all recursive functions. Find and write all the base cases and then write the solution for the problem assuming a simpler problem has already been solved.

    however as a programmer you should be aware what’s going on under the hood

    I’m not sure if you are talking about the concept of gotos or what happens when OP’s code is run. If it is the latter, then I have to say that most compilers very likely wouldn’t remove that recursive call in the final assembly. That’s why running the program with a large number results in a segfault. Because the stack overflowed, because it’s a recursive call.