...

View Full Version : Some Java recursion



MellyPie
01-23-2005, 06:04 PM
Hey y'all!
I'm a new un! Just learnin Java..

Anyway hope you guys can help....I've got some Java code


import java.io.*;

public class test{

public static void dude (int y)
{
if( y==0)
{
System.out.println("y="+y +" :Statement inside the if");
y+=1;
dude(y);
}

if(y==1)
{
System.out.println("y="+y+" :Statement inside the if");
y+=1;
dude(y);
}
System.out.println("y="+y+" Its caught the statement outside the if");
}
public static void main (String [] args)
{ int y=0;
dude(y);
}
}









Which compiles fine but produces unexpected results!
This is what it produces:

0 :Statement inside the if
1 :Statement inside the if
2 Its caught the statement outside the if
2 Its caught the statement outside the if
1 :Statement inside the if
2 Its caught the statement outside the if
2 Its caught the statement outside the if



I really dont understand why it is doing this as I would have expected an output of:


0 :Statement inside the if
1 :Statement inside the if
2 Its caught the statement outside the if
2 Its caught the statement outside the if


ie the first 4 lines! Why does it suddenly do y=1 again and so shove it thru the if statement again...and where are the last two "2 Its caught..." statements coming from?

Thanks for the help :)

mcq
01-23-2005, 06:21 PM
sorry, i dont understand that someone else will.

cfc
01-23-2005, 07:41 PM
Hmmm, that's weird. I rewrote it (I couldn't help it, sorry) with a switch in function dude, and it produced the expected output (0, 1, 2). Note that you don't have to import java.io



public class recursion {

public static void dude (int y)
{
switch (y) {
case 0:
case 1:
System.out.println("y = " + y + " :Inside the if");
y++;
dude(y);
break;
default:
System.out.println("y = " + y + " :Outside the if");
}
}

public static void main (String [] args)
{
int y = 0;
dude(y);
}
}


I also rewrote your code in a way that should function identically to the way it did before, but now it produces the output 0, 1, 2, 0 which is at least not as far off :confused:


public class recursion {

public static void dude (int y)
{
if (y == 0) {
System.out.println("y = " + y + " :Statement inside the if");
dude(y + 1);
}

if (y == 1) {
System.out.println("y = " + y + " :Statement inside the if");
dude(y + 1);
} else {
System.out.println("y = " + y + " :Statement outside the if");
}
}

public static void main (String [] args)
{
dude(0);
}
}


I'm sure someone that's brilliant at Java will come along and correct the newbish mistakes we're probably making...

mcq
01-23-2005, 08:49 PM
oh i sort of understand that now but it still seems confusing

KeZZeR
01-23-2005, 11:27 PM
If you've got the correct experience in java you should be able to explain this diagramatically listing what data shall be placed on the stack first, and then which shall come out. It goes from the inside out remember. I would go through it but i haven't got time

cfc
01-24-2005, 03:52 AM
It's all in how the function calls itself. I can't believe I didn't think of it earlier :p

When a function calls itself, it simply creates another instance (may be a bad word for it, but you get the idea) of itself and does not end unless you tell it to return or its entire body of code has been evaluated. This is simply demonstrated by the following simplified rewrite of your code and the explanation of why yours didn't work as you expected it to:

Proper output (0, 1, 2) produced by:


public class recursion {
public static void recurse (int x)
{
if (x <= 2) {
System.out.println(x);
recurse(x + 1);
}
}

public static void main (String[] argv)
{
recurse(0);
}
}


Here's the breakdown of your original code's output:
dude(0) --> first, print the number: 0; Increment the number for this function call, then call dude(1). (print 0)

dude(1) --> first, print 1; Increment the number for this function call; call dude(2). (print 1)

dude(2) --> print 2; (print 2)

dude(1) --> dude(2) has completed; print the same number incremented in dude(1) that dude(2) did not change because dude(2) was its own distinct function call. (print 2)

dude(0) --> dude(1) has completed; print the same number originally incremented in dude(0) (to simplify, print 1) and call dude(2) because we didn't use else if instead of if which means the variable has been incremented to 2; (print 1)

dude(2) --> print 2. (print 2)

dude(0) --> print 2 which the dude(0) specific variable was incremented to in the call to dude(2). (print 2)

Err... simple, right?

KeZZeR
01-24-2005, 09:49 AM
Simple enough :p

I just write out what goes on the stack and then what comes out. In fact, i've got an exam on recursion in Java tomorrow :)

JWizard
02-09-2005, 03:05 AM
First of all, Java has nothing to do with recursive analysis. Someone with no Java experience and who's an expert in algorithm analysis can solve any problem. Secondly, a brute force solution such as writing out the contents of the stack is a very simple-minded idea.

KeZZeR: Solve F(n) = F(n-1) - F(n-2) for n=500

This can be solved quite easily using mathematics, and would take a week to solve by writing out the stack contents (by the way it's a Fibonacci number, and has a much more efficient algorithm than this to be computed by).



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum