Little help with recursion

[denis_stoyanov]

Well i'm just starting to study recursion and i have a small problem. I'm trying to write a program which generate every six digit combination where every digit is used only one time. I've writed an iterative (i think this is the correct term) :

#include "stdafx.h"
using namespace std;

void main () {
	int a,b,c,d,e,f;
	long int n=0;
	

	for (a = 0; a < 9; a ++ )
		for (b = 0; b < 9; b ++ )
			for (c = 0; c < 9; c ++ )
				for (d = 0; d < 9; d ++ )
					for (e = 0; e < 9; e ++ )
						for (f = 0; f < 9; f ++ ) {
							n = a * 100000 + b * 10000 + c * 1000 + d * 100 + e * 10 + f ;
							if ( (a!=b) && (b!=c) && (c!=d) && (d!=e) && (e!=f))
								cout << "\n " << n;
						}
}

and now i'm trying to write a recursive version of it(completely wrong i guess):

#include "stdafx.h"
using namespace std;

long int check (long int n);

void main () {
	cout << "\n " << check(0);
}

long int check (long int n) {

	while ( n < 1000000) {
		if ((n/100000 != n/10000) && (n/10000 != n/1000) && (n/1000 != n/100) && (n/100 != n/10))
			return n;
		else check(n++);
	}
}

Can somebody help :?: ?

[Banfa]

Firstly your iterative version is highly in efficient. If you checked a != b between lines 10 and 11 then you could avoid all the loops and other checking when a == b. That is quite a lot of processing because you will cut out 9 * 9 * 9 * 9 = 6591 iterations of themain loop body.

You will need to include more { } pairs to properly block your loops.

Also notice I said 9 * 9 * 9 * 9 not 10 * 10 * 10 * 10? Your algorithm is wrong. Have you checked the output? Not a single number will contain the digit 9 because you have all your loop end condition wrong.

In your recursive version your method to isolate the digits does not work, consider the number 123456 and consider your attempt to isolate the 3rd digit n / 1000. 123456 / 1000 = 123. It clearly doesn't work. You need to use the % operator.

Also you have a while loop in the function. A loop like that in a supposedly recursive function is normally a clear sign of an error. recursion replaces iteration.

A recursive function should have an end condition. If the end condition is met the function returns otherwise the function recurses.

The whole recursion returns a single result. Your cout statement is outside the function in main so if the function was working the program would pront a maximum of 1 value. This is not what you want. The cout statement should be inside the recursive function.

A recursive function operating on a single variable is like a single for loop (usually). The way you have written your recursive function suggests you were trying for an implementation that you replace a itterative algorithm with a single loop. That is nothing like the actual iterative algorithm you are using which uses 6 loops.

If you try and call a recursive function recursively 1000000 times you are likely to have a problem with stack space usage. Your algorithm needs to be making less calls.