Understanding recursion

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.

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.

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.

Quote:

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.

Quote:

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.

Quote:

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

Quote:

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; }

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.