Thread: Understanding recursion - Pls help

  1. #1
    Registered User
    Join Date
    Sep 2009
    Posts
    1

    Understanding recursion - Pls help

    Hi,

    I am trying to learn how this recursive program leads to the answer that it gives.
    This code creates all permutations of a string given.
    It prints the answer right, but I dont understand how this work in the system memory - The logic - that it what it swaps and how.

    To understand that could sm1 please layout the first few steps (in terms of memory) on how it has been done?

    Code:
    #include <stdlib.h>
    #include <string.h>
    #include <stdio.h>
    int global = 0;
    void swap(char* src, char* dst)
    {
            char ch = *dst;
            *dst = *src;
            *src = ch;
    }
    /* permute [set[begin], set[end]) */
    int permute(char* set, int begin, int end)
    {
            int i;
            int range = end - begin;
            if (range == 1)
            {
                    global++;
                    printf("set%d: %s\n",global, set);
            }
            else
            {
                    for(i=0; i<range; i++)
                    {
                            swap(&set[begin], &set[begin+i]);
                            permute(set, begin+1, end);
                            swap(&set[begin], &set[begin+i]);       /* set back */
                    }
            }
            return 0;
    }
    int main()
    {
            char str[] = "abcd";
            permute(str, 0, strlen(str));
            return 0;
    }
    For instance - How I understand it works is -

    when permute is called -

    1) Calling Permute -
    set = "abcd"
    range > 1 [since 4-0]
    for..
    swaps(a,b) ???

    2) Recursion on permute(set,1,4) --is it still abcd??
    range>1
    swap(b,d) ???

    3)Recursion on permute(set,2,4) --is it still abcd??
    range>1
    swap(c,d) ???

    4)Recursion on permute(set,3,4) --is it still abcd??
    range==1
    print ??? What?

    5)Now when the function returns after (4) does after permute gets called?

    6) Why do we require 2 swaps and recursion in for loop?


    And so on...

    Thanks.

    Looking fwd to your replies.
    Last edited by jill123; 09-22-2009 at 11:00 AM. Reason: better layout

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So when you call permute, all those bits in parentheses are kind of important. If you start with abcd, the swap gives you bacd -- so when the next function call happens, that bacd is passed on the new function because, well, that's what lives inside the parentheses.

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    You can try putting in some debug printf statements in your swap and permute functions at some key places to see what's being called/swapped. This will allow you to walk through and understand what's happening.

    1) Calling Permute -
    set = "abcd"
    range > 1 [since 4-0]
    for..
    swaps(a,b) ???
    No, "a" and "b" are not swapped, the first time through the for loop i is 0 and so what's swapped are "a" and "a" (since both begin and begin+i are 0). For this run, nothing is effectively done to the string.
    2) Recursion on permute(set,1,4) --is it still abcd??
    range>1
    swap(b,d) ???
    Yes, the string is still "abcd" when we call the permute function recursively, but remember that we are entering a new instance of the permute function with it's own set of local variables and arguments separate from the instance that we just came from. There exists an instance, the previous one, where begin is 0 and end is 4. In this new instance, begin is 1 and end is 4. Whenever the current instance ends and is popped off the stack, we return to the previous instance with whatever values that instance has for it's local variables and arguments. We may end up going many levels deep before finally popping all the instances of the function off the stack and exiting back to main.

    Since we are in a new instance now, we again go into the for loop (i is still 0 since this is a new instance of the loop in a new instance of the function) and call the swap function. For this call, since i is still 0, we swap "b" with "b" since both begin and begin+i are 1. Again, nothing is modified in the string, it's still "abcd" at this point.

    3)Recursion on permute(set,2,4) --is it still abcd??
    range>1
    swap(c,d) ???
    The string is still "abcd" at the moment we call the permute function for the 3rd time (with begin 2 and end 4). We are now 3 levels deep into calling the function recursively. Again, we enter a new for loop with i starting out at 0 and we try and swap "c" and "c" (again, nothing happens to the string).
    4)Recursion on permute(set,3,4) --is it still abcd??
    range==1
    print ??? What?
    The string is still "abcd" when we call the function the 4th time with begin at 3 and end[/I] at 4. This time, when the range variable is checked and found to be 1 and we can finally print the string for the first time which is still "abcd". After this print, the 4th instance of the function gets popped off the stack and we are back to the 3rd instance (with begin 2 and end 4). The code reenters at the point just after the call to permute which is the call to the swap function. Since i is still 0 at this point, and begin and begin+i are both 2, we swap "c" and "c" which again do nothing (the string is still "abcd").

    Finally we've reached the end of the for loop for this instance of the function and i gets incremented to 1. Now when we go back into the loop and execute the swap with begin 2 and begin+i 3, we actually swap "c" and "d" and the string gets modified to "abdc".

    I'm not going to go any further than this, put in some print statements like I said and see for yourself what is happening. Try this and see what happens with the output:
    Code:
    void swap(char* src, char* dst)
    {
        static int i = 0;
        printf("Swap(%03d): Swapping %c with %c,",++i,*src,*dst);
        char ch = *dst;
        *dst = *src;
        *src = ch;
    }
    /* permute [set[begin], set[end]) */
    int permute(char* set, int begin, int end)
    {
        int i;
        int range = end - begin;
        static int level = 0;
        ++level;
        int this_level = level;
    
        if (range == 1)
        {
            global++;
            printf("\nPermute(%03d):set%d: %s\n\n",this_level,global,set);
        }
        else
        {
            for(i=0; i<range; i++)
            {
                swap(&set[begin], &set[begin+i]);
                printf(" set string is now \"%s\".\n",set);
                printf("Permute(%03d), i is %d, calling permute(\"%s\",%d,%d)\n",
                      this_level,i,set,begin+1,end);
                permute(set, begin+1, end);
                swap(&set[begin], &set[begin+i]);       /* set back */
                printf(" set string is now \"%s\".\n",set);
            }
        }
        return 0;
    }
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    The program written as is gives all the combinations of the different letters but it uses a mixture of iteration and recursion to do the job.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with understanding a recursion function
    By CS_Student8337 in forum C Programming
    Replies: 7
    Last Post: 02-10-2009, 06:52 AM
  2. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  3. Understanding recursion
    By caduardo21 in forum C Programming
    Replies: 4
    Last Post: 08-19-2005, 06:06 PM
  4. Problem of understanding recursion
    By ixing in forum C Programming
    Replies: 2
    Last Post: 05-02-2004, 03:52 PM
  5. help me pls..... :(
    By mocha_frap024 in forum C++ Programming
    Replies: 2
    Last Post: 02-22-2002, 10:46 AM