Question about recursion.
Given the following program that calculate all the permutations on a string
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void rotate(unsigned length, char *string)
{
char save;
save = *string;
while(--length)
{
*string=*(string+1);
++string;
}
*string = save;
}
void permute(unsigned length, char *string, unsigned depth)
{
if (length == 0)
printf("%s\n",string-depth);
else
{
unsigned count;
for (count = length ; count > 0; --count)
{
permute(length-1,string+1,depth+1);
rotate(length,string);
}
}
}
int main(int argc, char **argv)
{
while (--argc)
{
char *source = malloc(strlen(*++argv)+1);
if (source)
{
strcpy(source,*argv);
printf("\nPermuting \"%s\"\n",source);
permute(strlen(source),source,0);
free(source);
}
}
return EXIT_SUCCESS;
}
How come when I pass the string "chad", the permute() function gets called like 4 times before it executes the first rotate() function. I thought that the rotate() function would have gotten executed right after the call to premute(). Here is what backtrace showed yielded
#0 permute (length=0, string=0x804a00c "", depth=4) at perm.c:29
#1 0x080484df in permute (length=1, string=0x804a00b "d", depth=3) at perm.c:39
#2 0x080484df in permute (length=2, string=0x804a00a "ad", depth=2) at perm.c:39
#3 0x080484df in permute (length=3, string=0x804a009 "had", depth=1) at perm.c:39
#4 0x080484df in permute (length=4, string=0x804a008 "chad", depth=0) at perm.c:39
#5 0x0804857f in main (argc=1, argv=0xbffff058) at perm.c:62
