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.

CodePudding user response：

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;
}

CodePudding user response：

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