Tracing recursion calls

Question

I'm learning the concept of recursion and, to pratice my knowledge, I wrote the following program.

#include <bits/stdc++.h>

using namespace std;

int c = 0;

int add(int a) {
  if (a == 0) {
    return c;
  }
  c = c + 1;
  add(a - 1);
  cout << "Hello";
}

int main() {
  int x = add(6);
  cout << "Final " << x;
}

It produces this output, which is not what I expected:

HelloHelloHelloHelloHelloHelloFinal 5134464

Why the program is not terminating when the a==0 condition is satisfied and it returns the final result to the main function?

Instead of that, it's printing "Hello" 6 times, but the output statement is after the recursion call.

Why code after the recursion call is still executed multiple times?

I expected it would never be executed.

I'm still trying to understand how recursion works, so I'd like to know what exactly is happening here.

return means only return from the current function call, not from the whole recursion stack. — gerum, Dec 22 '21 at 11:54
You are not returning any value except for the case when a is 0. try putting the add(a-1) at the end and add a return statement like this `cout…; return add(a-1)` — Gian Laager, Dec 22 '21 at 12:10
strictly speaking your code could print any output, because not returning a value from `add` invokes undefined behavior. Compilers warn about this: https://godbolt.org/z/81xfPdjdc — 463035818_is_not_an_ai, Dec 22 '21 at 12:32
(OT: [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h)) — Biffen, Dec 22 '21 at 13:29

kesarling He-Him · Answer 1 · 2021-12-22T12:19:48.777

0

Thumb Rule: Return statement in a recursive function should preferably be the last statement of the function

You see, you're returning c, but you are not storing it anywhere!

I believe this is the code you're looking for:

#include <iostream>

void practiceRecursion(const int& a, int& c) {
    if (a != 0) {
        c++;
        practiceRecursion(a-1, c);
    }
}

int main() {
    int a = 6;
    int c = 0;
    practiceRecursion(a, c);
    // whatever you wish to do with c
    return 0;
}

edited Dec 22 '21 at 12:19

answered Dec 22 '21 at 12:08

kesarling He-Him

1,944
3
14
39

Why do you return c and use it as an output parameter? – gerum Dec 22 '21 at 12:09
We could've just as easily done `int num = practiceRecursion(6, 0);` (Although then I wouldn't have used the `int&`) – kesarling He-Him Dec 22 '21 at 12:11
I do not understand your answer or you do not understand my question. I want to know why the function practiceRecursion has an output parameter and returns the same value. So you hand back the same value twice. – gerum Dec 22 '21 at 12:17
ah! Oh, right, no need to return it – kesarling He-Him Dec 22 '21 at 12:19

score 0 · Accepted Answer · answered Dec 22 '21 at 14:35

The main issue of the posted function is that it has undefined behavior.

int add(int a) {     // Note that this function is supposed to return an int.
  if (a == 0) {
    return c;        // <- Ok, recursion stopped, first exit point.
  }
  // else 
  c = c + 1;
  add(a - 1);        // Recursive call. When it returns, the execution continue
                     // from here, it does not jump diretly back to main.
                     // That's exactly what would happen if instead of `add`
                     // here, there were a call to another function, say `foo(a-1);`
                     // You would expect the excution to continue after it, don't you?
  cout << "Hello"; 

  // Here a return statement is missing (second exit point) => UB
  // The strange number you see in the output is a result of that. Maybe 
  // return c; 
}

What you see when the program is executed is something like

call to add() with argument 6
    call to add() with argument 5
        call to add() with argument 4
            call to add() with argument 3
                call to add() with argument 2
                    call to add() with argument 1
                        call to add() with argument 0
                            return 0
                        print "Hello"
                        return garbage (ignored)
                    print "Hello"
                    return garbage (ignored)
                print "Hello"
                return garbage (ignored)
            print "Hello"
            return garbage (ignored)
        print "Hello"
        return garbage (ignored)
    print "Hello"
    return garbage, which is stored in x
print "Final" and whatever is in x

Tracing recursion calls

2 Answers2