Question about recursion.

This is a discussion on Question about recursion. within the C Programming forums, part of the General Programming Boards category; Given the following program that calculate all the permutations on a string Code: #include <stdio.h> #include <stdlib.h> #include <string.h> void ...

  1. #1
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195

    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

  2. #2
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote 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);
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  3. #3
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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()?

  4. #4
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195
    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.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote 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?

  6. #6
    and the Hat of Clumsiness GanglyLamb's Avatar
    Join Date
    Oct 2002
    Location
    between photons and phonons
    Posts
    1,109
    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 ).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. iteration and recursion question
    By Stonehambey in forum C++ Programming
    Replies: 3
    Last Post: 03-19-2008, 06:16 PM
  2. simple recursion question
    By salvadoravi in forum C Programming
    Replies: 4
    Last Post: 12-30-2007, 06:53 AM
  3. Design layer question
    By mdoland in forum C# Programming
    Replies: 0
    Last Post: 10-19-2007, 04:22 AM
  4. Recursion vs multiple functions
    By PJYelton in forum C++ Programming
    Replies: 4
    Last Post: 12-29-2002, 07:52 PM
  5. Very simple question, problem in my Code.
    By Vber in forum C Programming
    Replies: 7
    Last Post: 11-16-2002, 02:57 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21