Recursive function

[Pecvx]

I don't understand exactly what is going on here when you for example call func("aaa123"). I think it'll first call func("aaa123"), func("aa123"), func("a123"), func("23") and so on until we reach the null, but when exactly is the cout statement following the recursive call executed?

void func(char* Cstr) {
if (*Cstr != '\0') {
func(Cstr + 1);
cout << *Cstr;
}
}

[keskiverto]

After the recursive call has returned.

func("abc");
// expands to
if ('a' != '\0') {
  func( "bc" );
  cout << 'a';
}
// expands to
if ('a' != '\0') {
  if ('b' != '\0') {
    func( "c" );
    cout << 'b';
  }
  cout << 'a';
}
// expands to
if ('a' != '\0') {
  if ('b' != '\0') {
    if ('c' != '\0') {
      func( "" );
      cout << 'c';
    }
    cout << 'b';
  }
  cout << 'a';
}
// collapses to
cout << 'c';
cout << 'b';
cout << 'a';

[dhayden]

It might be easier to understand what happens with some extra output:

#include <iostream>
using std::cout;

void
func(char *Cstr)
{
    cout << "Entering func(\"" << Cstr << "\")\n";
    if (*Cstr != '\0') {
	func(Cstr + 1);
	cout << "func(\"" << Cstr << "\") prints "
	     << *Cstr << '\n';
    }
    cout << "Leaving func(\"" << Cstr << "\")\n";
}

int main()
{
    func("hello");
}

Entering func("hello")
Entering func("ello")
Entering func("llo")
Entering func("lo")
Entering func("o")
Entering func("")
Leaving func("")
func("o") prints o
Leaving func("o")
func("lo") prints l
Leaving func("lo")
func("llo") prints l
Leaving func("llo")
func("ello") prints e
Leaving func("ello")
func("hello") prints h
Leaving func("hello")

[zapshe]

Once the function calls "func" for the LAST time (when it reaches the null finally), then it'll skip over the if statement and finally the previous function calls will start to finish. So after the Final Function Call, it'll finally progress to Line 4, finish, go to previous function call - progress to Line 4, finish, and so on until it does so for the very first function call.

So the recursive function will cout in reverse order of the function calls. This is because NONE of the iterations of the function will ever reach the "cout" until the it does the function call before it. Only when you reach and finish the last function call will it actually start printing to the screen.

[Pecvx]

Thanks all, this forum has really been to great help for understanding C++/programming in general!

what I don't quite understand, from @dhayden's example, is how we "get back" inside the if-statement after

Leaving func("")

I understand a recursive function which is set up like this:

 int factorial(int x) {
if (x==1) {
return 1;}
else { return x*factorial(x-1); }} 

and I assume it's much the same in this case, but exactly how I'm not sure.

[dhayden]

what I don't quite understand, from @dhayden's example, is how we "get back" inside the if-statement after

Consider this code:

void otherFunc(char *cp)
{
    cout << "I am another function called with " << cp << '\n';
}

void func(char* Cstr) {
    if (*Cstr != '\0') {
        otherFunc(Cstr + 1);  // call another function
        cout << *Cstr;    // then print the string
    }
}

Here func() is the same as yours with just one exception: it calls otherFunc() instead of func().

Do you see how the program calls otherFunc()? See how otherFunc() runs and when it returns, the program continues inside the if statement?

Of course you do :). This is easy. It's just a normal function call.

The key is that when you call a function recursively, it's no different! Returning to my program, after printing "Leaving func("")", that call to func() returns. Where was it called from? It was called from inside the if statement, so that's where it returns to! Each call returns to the point where it was called.

It might also help to realize that, even though the program executes the same code several times, each call creates its own separate Cstr parameter and return address. The returns address is like a hidden parameter to the function that tells the program where to resume execution when it returns. That's how it knows to return to the if statement for the recursive calls, and the main program for the first call.

Does this make sense?