convert nested for loop to recursion

[Sue]

I have this code with nested for loops - I need to convert this to a
recursive function. There are 3 nested for loops so the results are 3
digit numbers, example 279: 289: 345: 346: 347: 348: 349: 356: 357:
358: 359: 367: 368: where the 2nd digit is always larger than the
first, and the 3rd digit is always larger than 2nd. If I need 4 digit
numbers then I have to write 4 for loops, 5 digits - 5 for loops and so
on.

If I convert this to a recursive function I should be able to pass the
number of digits needed, 3, 4, 5 etc as argument to the function.

I am finding it difficult to understand recursion so any help in the
right direction will be extremely helpful. Thank you very much!


int a[] = {0, 1,2,3,4,5,6,7,8,9};

for (int i =0; i<a.length; i++)
for (int j=0; j<a.length; j++)
for (int k=0; k<a.length; k++)
{
if (a[j]>a & a[k]>a[j] ) {
System.out.println(a + "" + a[j] + "" +
a[k]);
}
}

 

[Flo 'Irian' Schaetz]

And thus, Sue spoke...

I have this code with nested for loops - I need to convert this to a
recursive function.

Why? Recursion is not often a good thing, in many cases it's more
complex, harder to read, needs more memory, etc. Anyway, doing it the
way you do doesn't seem to be a good idea, either...

I would suggest looking at the array and see, that it's already sorted.
So if your first digit is a 0, all possible 2nd digits are right of it
and if you need 3 digits, you may only go until the end-1 - so all
possible 2nd digits for "first digit 0" and "3 digits total" are 1-8. If
you can rely on the fact that every digit exists only once in the array
and it's always sorted (perhapy by doing it yourself), it's rather easy.

Flo

 

[Jeff]

And thus, Sue spoke...


Why? Recursion is not often a good thing, in many cases it's more
complex, harder to read, needs more memory, etc. Anyway, doing it the
way you do doesn't seem to be a good idea, either...

I would suggest looking at the array and see, that it's already sorted.
So if your first digit is a 0, all possible 2nd digits are right of it
and if you need 3 digits, you may only go until the end-1 - so all
possible 2nd digits for "first digit 0" and "3 digits total" are 1-8. If
you can rely on the fact that every digit exists only once in the array
and it's always sorted (perhapy by doing it yourself), it's rather easy.

Flo

It's really more of a looping problem than a recursion problem. You can
generate one digit, then with recursion generate the next two, but then
generating the _next_ number in the sequence is problematic. Next and
Sequence being operative terms that suggest Loop. So, unless this is
homework that requires recursion, I'd suggest nested loops.
/js

 

[Chris Smith]

I have this code with nested for loops

I'm assuming this is just code written for your own amusement or
edification. If not, then a number of suggestions for design changes
would apply.

If I need 4 digit numbers then I have to write 4 for loops, 5 digits
- 5 for loops and so on.

Okay, that's a start. So the general technique for recursion is to do
the following:

1. Generalize the problem.
2. Identify the simplest possible instance of the generalized problem.
3. Express the top-level problem as an instance of the generalized one.

In this case, here's a basic idea how I would proceed:

1. The generalized problem becomes something like the following. Given
an ordered pair (x,k,n,a) where 'x' is a string, 'k' and 'n' are natural
numbers, and 'a' is an array of natural numbers: find all elements of
'a' that are greater than 'k', and process the string that you get by
concatenating the new element onto the end of 'x'.

2. The simplest possible case is n=0. In that case, you want to
consider 0 more levels of depth, meaning that 'x' is the answer.

3. The top-level problem is ("",-1,n,a) where n is the number of levels,
and a is the array. I fudged k a little, since I called it a natural
number but I needed something smaller than all possible natural numbers
for the top-level problem.

Hope that helps. See if you can knock out the implementation from
there.