void foo3(char *x)
{
if (!*x) return;
foo3(x+1);
printf("%c ",*x);
}
If for example x points to an array ar[]="abc", why does it print "cba"? Why does it even print if it will just keep re-entering the function over and over until the if is true then it returns.
How does it print?
If you call foo3("hi"), the first thing it does is look at the 'h' pointed to by the parameter x. Since that is non-zero, it calls foo3("i")--meaning that it passes the address of the rest of the string.
foo3("i") looks at the 'i', sees it's non-zero, and calls foo3("") -- technically it passes the address of the null terminator to the original string.
foo3("") looks at the null terminator, and returns.
foo3("i") prints the 'i' and returns.
foo3("hi") prints the 'h'.
The function works because it makes the recursive call before printing the "current character", so that the rest of the string will be printed before it.
The call stack would look like this (pseudo-code) which should show how and why it prints 'cba'.
x is a C-style array 'a', 'b', 'c', '\0'
call foo3(x)
call foo3(x+1)
call foo3(x+2)
call foo3(x+3)
return to foo3(x+2)
print(x+2) 'c'
return to foo3(x+1)
print(x+1) 'b'
return to foo3(x)
print(x) 'a'
return to calling program
We can extract a general rule of thumb from this: If you process some data and then recur, you're working on the data from front to back; if you recur then process some data, you're working on the data from back to front. You can see this if you reverse the last two lines:
void foo3(char *x)
{
if (!*x) return;
printf("%c ", *x);
foo3(x + 1);
}
The data comes out in the original order as we're now processing some data and then recurring.
@cdlane has a point. This example with two printf will help you understand the mechanism behind recusrion.
#include <stdio.h>
void foo3(char *x)
{
printf("%c=\n",*x);
if (*x=='\0') return;
foo3(x+1);
printf("%c ",*x);
}
int main(void)
{
foo3("abc");
return 0;
}
cbaRather, it prints:c b a