Recursion! Don't understand :(

[Bman900]

So there is this code I found that does exactly what I need but I don't understand it:

/* function to swap array elements */

void swap (int v[], int i, int j) {
	int	t;

	t = v[i];
	v[i] = v[j];
	v[j] = t;
}

/* recursive function to generate permutations */
void perm (int v[], int n, int i) {

	/* this function generates the permutations of the array
	 * from element i to element n-1
	 */
	int	j;

	/* if we are at the end of the array, we have one permutation
	 * we can use (here we print it; you could as easily hand the
	 * array off to some other function that uses it for something
	 */
	if (i == n) {
		for (j=0; j<n; j++) printf ("%d ", v[j]);
		printf ("\n");
	} else
		/* recursively explore the permutations starting
		 * at index i going through index n-1
		 */
		for (j=i; j<n; j++) {

			/* try the array with i and j switched */

			swap (v, i, j);
			perm (v, n, i+1);

			/* swap them back the way they were */

			swap (v, i, j);
		}
}
			
/* little driver function to print perms of first 5 integers */

int main () {
	int	v[5], i;

	for (i=0; i<5; i++) v[i] = i+1;
	perm (v, 5, 0);
	exit (0);
}

So my question is, I see how the program prints out the first array but how does it get back into the else statement if the "if" statement stops the function? Basically once i == n and the number get printed, how does it move on to the next perm() function?

[Pax]

It works the other way around. It will keep going on the else until the if condition is true, at which point it finishes and returns to the calling function.

[Bman900]

Yes I get that it will stop once the if is met but that will only print the array once, how does it print the permutations 120 times? Is perm called again in the main function from where it left off?

[Pax]

Ah, sorry. Didn't quite understand what you were asking.

Anyway, line 30 says:
for (j=i; j<n; j++)

Perm is calling itself quite a few times in each step of the iteration. So each level will fire off another n-i runs of perm, which will fire off n-i themselves until the if statement is met.

[Bman900]

Man this is really hard to understand. In class we made another version of this code and here is how it looks like.

http://i67.photobucket.com/albums/h306/BmanV2/helpcopy.jpg

[Browni3141]

Recursion is a little difficult to understand for beginners, and me, as I am also a beginner, but it's really only a different kind of loop. Any recursive function can also be written as a for, while or do while loop. This is basically the way it works:

1. The function is called
2. An exit condition is checked
3. Code within the function is executed if the exit condition was false
4. Function is called again
5. Process continues until the exit condition is met

In the example in your question, the function is called and run through until the condition (i == n) is met. Then the numbers in the array v[] are printed, and the function has to back out. I say back out because I don't know what to actually call it. Can anyone else explain more technical details on recursive functions?

[Bman900]

Well when i == n the permutation doesn't end, this is why am confused. It goes back and calls itself magically or by logic which I don't understand. Can some one explain what happens in this loop after the condition is met once?

[Browni3141]

I must admit I'm confused as well, but I have a question of my own. On line fifty you have exit (0);. Is this the same thing as return 0;?

[ne555]

You have a stack. When you call a function, it pushes in the top. When the function ends it pops from the top.
Only the function that is at the top is executed.
Now, do a desk test.

[Bman900]

Browni3141 yes that is the same as return. An ne555 can you elaborate more on that since it sounds very confusing.

[ne555]

Try to run your program trough a debugger, so you can see the functions calls and the flow of the program.
Suppose you call your function with perm(array, 2, 0). Now to the array be printed i==n so it must be call with perm(array, 2, 2) (A).
Who make that call?
It was a perm function where i!=n(B).
When (A) ends the program will continue through its "parent" (B), that will keep launching more recursive calls, because the for loop.

Do a desk test, print debug information (like the parameters of the function when is called), play with your program.

[S6k9GNh0]

- exit(0) is not that same as return 0 in main although similar: http://www.cplusplus.com/reference/clibrary/cstdlib/exit/

- recursion is generally a bad practice. It can normally be avoided with cleaner and less obfuscated code. Recursion tends to be king in problems with infinite loops.

[Bman900]

So I should not worry too much about it as there are better ways to solve problems? Even in class we only spent about 1 hour on the subject. I thought this would be super important in programing.

[S6k9GNh0]

Oh no, recursion is important! It some cases, recursion just seems like the way to go. I'm saying though that it gets overused and you need to be very careful when using it. If recursion seems confusing to you, then don't use it (as in, learn the concept and if recursion doesn't seem right for the piece of code you're writing, don't use it)

[Disch]

More often than not, recursion is better to be avoided. About the only time I use recursion is for navigating tree-like structures... which is very seldom.

IMO, recursion is taught far too early in most programming courses. It makes it come across as more commonplace than it actually is. It really shouldn't be taught to beginners.

[Bman900]

Well I understand the basic concepts of it so am going to leave the complicated stuff for when I get better. Thank you all for the help!