Recursion in all it's horrible glory

[jisoo22]

Hello all,

I'm just starting out and learning Java right now, so please bear with me =) I'm working on a school assignment that asks me write two methods, one iterative and the other recursive. I have no problem creating the iterative but the subject of recursion has always been kinda hazy to me. I have a working recursive method but I get stack overflow errors. Here's the code I have right now:

    public long powerMod1( long x, long y, long n ) {

		long temp = 1;
		long temp2 = 0;

		for (int i = 1; i <= y; i++)
		{
			temp = temp * x;
			temp2 = temp % n;
		}
		return temp2;
	}


    //powerMod2 method goes below

	public long powerMod2( long x, long y, long n ) {

		long temp;
		long temp2 = powerMod2( x, y-1, n);

		if (y == 1)
			return x%n;
		else
			temp = (x%n * temp2)%n;
			return temp;

	}

Basically what the program does is take in three arguments (x, y, and z) and computes X to the power of y, then the mod of z. So the equation looks like (x^y)mod z. I'm not quite sure if this is enough information, it it isn't just let me know. Can anyone show me how to implement recursion in this particular instance? Any help is appreciated.

Thanks,
Jisoo22

 

[sedj]

Here is a very simple example of recursion - you can modify it for your needs ...

public class RecEx {
   public void recur(int x) {
        if (x < 100) {
	   x++;
	   System.out.println(x);
           recur(x);
    	}
   }
 
   public static void main(String args[]) {
	RecEx re = new RecEx();
	re.recur(0);
   }
}

 

[jisoo22]

I'm getting an idea but I'm still a little confused on how to implement it. Here's what I have for this method:

public long powerMod3( long x, long y, long n ) {

		long temp = x % n;
		long temp2 = 0;

		if ( y == 1 )
			return temp;
		else
			while ( y != 1 )
				temp2 = (x % n * powerMod3( x, y-1, n)) % n;
				return temp2;

	}

It results in an infinite loop though, when I compile it nothing happens but the computer keeps processing. Anyone have any ideas on how to straighten this out? Again the essential equation to think about is (x^y)%n. My previous methods usually just multiplied X by itself Y times, then took the MOD of N for the answer (as seen from powerMod1 up in the first post). I'm trying to accomplish the same thing here.

Thanks,
Jisoo22

 

[palbano]

>> It results in an infinite loop though

>> while ( y != 1 )

Of course... because you provide no mechanism for y to be assigned the value of 1

-pete

 

[sedj]

jisoo22,

I think you are missing the point of recursion a bit here - recursion is where a method is called from within itself, in order to produce some kind of desired result. An excellant real-world implementation of recursion is determining a file system structre, or searching within a file system for a given file ... you start off with one directory, and in each recrsive loop, pass the new directory listed into the method - hence drilling dowm through the directories.

Your method above has the problem that it accepts 3 numbers as the arguments, but only returns 1. So you cannot implement recursion from that method, because you need to pass into the method call three args.

Take a look again at the example I gave you before !

 

[palbano]

Actually recursion is the act of leveraging the stack to produce a sequence of desired activities. This gives you the flexibility of inside out or outside in processing based on the natural behavior of a stack.

>> recursion is where a method is called from within itself

In today's OO languages, like Java, object based recursion is much more prevalent.

"But, that's just my opinion... I could be wrong".
-pete