Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 8 of 8
  1. #1
    New to the CF scene
    Join Date
    Jan 2005
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Some Java recursion

    Hey y'all!
    I'm a new un! Just learnin Java..

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

    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

  • #2
    mcq
    mcq is offline
    New Coder
    Join Date
    Jan 2005
    Location
    northren ireland Age:14
    Posts
    23
    Thanks
    0
    Thanked 0 Times in 0 Posts
    sorry, i dont understand that someone else will.

  • #3
    cfc
    cfc is offline
    Regular Coder
    Join Date
    Dec 2004
    Location
    Keswick, Ontario
    Posts
    251
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

    Code:
    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
    Code:
    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...

  • #4
    mcq
    mcq is offline
    New Coder
    Join Date
    Jan 2005
    Location
    northren ireland Age:14
    Posts
    23
    Thanks
    0
    Thanked 0 Times in 0 Posts
    oh i sort of understand that now but it still seems confusing

  • #5
    Regular Coder
    Join Date
    Oct 2004
    Location
    England
    Posts
    282
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

  • #6
    cfc
    cfc is offline
    Regular Coder
    Join Date
    Dec 2004
    Location
    Keswick, Ontario
    Posts
    251
    Thanks
    0
    Thanked 0 Times in 0 Posts
    It's all in how the function calls itself. I can't believe I didn't think of it earlier

    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:
    Code:
    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?
    Last edited by cfc; 01-24-2005 at 03:58 AM.

  • #7
    Regular Coder
    Join Date
    Oct 2004
    Location
    England
    Posts
    282
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Simple enough

    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

  • #8
    New Coder
    Join Date
    Feb 2005
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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).


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •