Recursive functions

[RapidX]

Hello everyone,

In a book I'm looking into, I came across recursive functions. I understand the basic idea of how recursive functions work, but can anyone tell me how the program below prints out the string in reverse?

//This is a recursive function example

#include <iostream>
using namespace std;

	void reverse(char *s);
	
	int main()
	{
		char str[] = "This is a test string";
		
		reverse(str);
	
		return 0;
	}
	
	void reverse(char *s)
	{
		if(*s)
		{
			reverse(s+1);
		}
		else
		{
			return;
		}
		
		cout << *s;
	
	}

If it's calling itself each time and going to the next character each time(s+1) until it reaches the null terminating point of the string and cout-ing each time it is called, isn't it suppose to cout each character in non-reverse instead of reverse?

Any input on this is greatly appreciated!

[Dacster13]

well actually what it does is it looks for the end of the string first. if s isn't the null character then it just goes on to the next.

The real magic actually begins after the program returns, after it returns it will go back to the function that called it, which is also reverse on line 21 and start executing the rest of the code. Since reverse(s+1) is inside the if statement it will reach the end of the if statement and bypass the else statement entirely. Then it will cout the character parameter it has which is the last character on the string.

After that, it will find the end of the function. So it will return again to the function that called it, which is on line 21 again the reverse(s+1), it will find the end of the if, skip the else part cout the second to last character then return to the function that called it again. I hope you're seeing a pattern here now.

It will repeat that process until the first reverse function called returns to the function that called it which is the main function and continue executing right after the last statement so it will go back and start executing the code in main from line 13 onwards. Finally, it will find the return 0; statement and will close the program. I hope that makes sense.

[WilliamW1979]

This shouldn't work at all, char [[ is different from char * to a compiler so it should error out. What is the point of the reverse function, what is it you are trying to accomplish because it you are trying to detect a null ending character, then test each character for '\0'. Maybe I am misunderstanding what you are trying to do.

[RapidX]

It works and got no errors during compile.

There is no point really. I got this from a book and trying to understand recursive functions and the above example I just can't get quite seem to grasp the logic behind it. I'm not sure how it looks for the end of the string first.

This is how the book explains it:

The reverse( ) function first checks to see if it has been passed a pointer to the null
terminating the string. If not, then reverse( ) calls itself with a pointer to the next
character in the string. When the null terminator is finally found, the calls begin
unraveling, and the characters are displayed in reverse order.

[Disch]

Each time the reverse function is called, it calls reverse again to look at the character after it. So basically what it's doing is printing the following character before the current character.

I tweaked the function here so that it's a little easier to follow. Note this function does the EXACT SAME THING as the one you posted:

void reverse(char* s)
{
    if(*s)    // if this is not the NULL terminator at the end of the string...
    {
        reverse(s + 1);  // print the character after this one
        cout << *s;  // then after that is printed, print this one
    }
}

So for example, let's say we have the string "ABCD": reverse("ABCD");

void reverse(char* s)  // s is "ABCD"
{
    if(*s)  // *s is 'A'.  Which is not the null terminator, so this if statement executes
    {
        // print the characters after the 'A' first
        reverse(s + 1);  // this calls reverse with "BCD"
        cout << *s;  // then this prints 'A'
    }
}

When called with "BCD":

void reverse(char* s)  // s is "BCD"
{
    if(*s)  // *s is 'B'.  Which is not the null terminator, so this if statement executes
    {
        reverse(s + 1);  // this calls reverse with "CD"
        cout << *s;  // then this prints 'B'
    }
}

So what ends up happening is reverse gets called 4 times deep. The deepest is the first to print its character, then as the reverse calls exit, the previous calls print their character:

call reverse
    call reverse
        call reverse
            call reverse
                do nothing (null terminator found)
            print 'D'
        print 'C'
    print 'B'
print 'A'

[RapidX]

Thank you Disch for that wonderful illustration.

What's strange(well to me) is how the deepest is the first to print its character when each time the reverse function is called, it cout's the next letter from the beginning.

[WilliamW1979]

Ok, so you were suppose to declare a char * originally, not a char [] to get this to work. They gave you the reverse function and you were just trying to use it to see what it does! That explains a lot and personally I would of used a for loop to do the same thing this did, I wonder what would be faster though? Would make for an interesting test!