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

Originally Posted by cdalten

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().

Well, the length is 4. And it is recursion, so until the recursing ends, rotate will not get called, right?

Perhaps throw a debug line in.

Code:

void permute(unsigned length, char *string, unsigned depth) 
{ 
   printf("length = %u, string = \"%s\", depth = %u\n", length, string, depth);

This would be an excellent time to try out your debugger's step-into ability.

Let me ask you this: Inside of permute() when it recursivily calls itself, which function will it hit first: permute() or rotate()?

When the function permute() calls itself recursively, it hits permute() first. I guess the thing that is/was throwing me is that rotate() doesn't get execute right after the permute() function. Or at least it appears that way.

Originally Posted by cdalten

When the function permute() calls itself recursively, it hits permute() first. I guess the thing that is/was throwing me is that rotate() doesn't get execute right after the permute() function. Or at least it appears that way.

Ah, but it does!!!
rotate is definately called straight after permute. However, what does permute do?

Well permute calls permute then rotate, so after thios new call to premute that calls rotate, you'll call rotate. Oh but that call to permute also calls permute and then rotate, so after calling permute which calls permute which calls permute, and then calls rotate, and then exits and calls rotate, it will call rotate... etc...

Getting it yet?

cdalten google for "recursion box method" it will show you exactly what is going on at which iteration.

http://www.cs.wmich.edu/~bhardin/Spr.../recursion.pdf explains the box method relatively well ( I would give the presentation of my programming class but they are not in english so + they're probably copyrighted ).