CODEWITHSUNDEEP
c++11recursion
Eehenhyu
Eehenhyu

Reputation: 1

(C++)Recursive function - don't know why this decrements

I'm just starting with recursive functions and know a some of how c++ works but I really don't understand how this code works:

    void q9_draw_triangle(int a, int b) {

        // a is the starting point, b is the end
        if (a > b) return;

        // print pattern first
        for(int i = 0; i < a; i++){
            std::cout << "-";
        }
        std::cout << std::endl;

        // call on triangle where a is incremented once
        q9_draw_triangle(a+1,b);

        // print pattern last
        for(int i = 0; i < a; i++){
            std::cout << "-";
        }
        std::cout << std::endl;

    }

I get how the upper half works, from q9_draw_triangle(a + 1,b) and up, but not the last for loop. When I stepped through this code using a debugger,once a > b happened it jumped to the last closing brace, then to the last for loop, and then started drawing the second half of the triangle and decrementing itself back down to the starting a value. I have no idea why this happened or how one would know to do this to decrement.

EDIT: Just in case further clarification is needed, say my inputs were a = 3 and b = 7. The first part from q9_draw_triangle(a + 1,b) and up would draw 3 lines, then 4,5,6,7. Then it goes to the last closing brace and then to the last for loop and draws 7; back to the last closing brace, back to the for loop and draws 6, then repeat for 5,4,3. Why does it do this? It never goes above the last for loop again and decrements itself and that's what I don;t understand. Then when it gets to a = 3 it finally steps out of the function, how does it know to do this?

Any help in understanding this is appreciated!

Upvotes: 0

Views: 34

Answers (2)

rzippo
rzippo

Reputation: 1059

Let's see the structure of this function as

print_block(a)
       recursive_call(a+1, b)
print_block(a)

This structure makes so that each recursion level "sandwitches" the successive ones. For example if we have a=1, b=2 the resulting call sequence would be

print_block(1)
       print_block(2)
               recursion stops: 3>2
       print_block(2)
print_block(1)

When the recursion stops the innermost call a=3 returns without any print or other calls. The control will then pass to its caller, that is a=2 which will print and return, passing control to a=1 which prints and returns to the original caller (probably main). You can see then why a appears to decrease: we're now traversing out of the recursion in the inverse order.

Upvotes: 1

travisjayday
travisjayday

Reputation: 814

Recursion is when a function calls itself, so you end up with a hierarchy of functions. If I defined a recursive function void func(int a), then the hierachy would look like this. 

func(1) 
   - func(2) 
        - func(3) 
             - ...

After some condition is met, for example a > 5, then the function returns early, and returns to the function that called it (the parent function). Then the parent function runs it's code until it returns, thereby going back to its parent function, and so on.

For examples of how recursion works, try googling it. This looks like a good place to start

https://www.codeproject.com/Articles/32873/Recursion-made-simple

I've commented the code to explain what's going on. It makes sense to me, but I hope it will make sense to you too. 

void q9_draw_triangle(int a, int b) {

    // this is our condition; this states when to stop the recursion
    if (a > b) return;

    // print current line
    // this loop draws the horizontal lines 
    // if a = 3, then it will draw ---
    for(int i = 0; i < a; i++){
        std::cout << "-";
    }
    std::cout << std::endl;

    // now that the current line was drawn, draw the next line
    // so if a = 3, now in the next function a will be 4
    // so the next function will print ----, which gives us an output of
    // ---
    // ----
    q9_draw_triangle(a+1,b);  // this jumps back up to the top of the function and reruns the function with a+1 until a > b. 

    // once a > b, the functions return one by one and the follwoing loop is run
    // in our example, a was 3 and then 4. If b was 4, then in our next iteration a would be 5, 
    // and the recursive function would simply return because a > b.
    // this code is run once the child function returns. So a would be 4 again, printing ----
    // this gives an output of 
    // ---
    // ----
    // ----
    for(int i = 0; i < a; i++){
        std::cout << "-";
    }
    std::cout << std::endl;
    // here the function retunrs again, so the we get back to the second loop 
    // and a will be 3 again.
    // so the total output is 
    // ---
    // ----
    // ----
    // ---
}

Upvotes: 1

Related Questions