Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 13 of 13

Thread: how to trace recursion variables in a recursive method

  1. #1
    Member
    Join Date
    Mar 2009
    Posts
    91
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default how to trace recursion variables in a recursive method

    guys, is there any way to trace the variables and calls in netbeans for recursive methods? I'm trying to understand the behavior of the "primeFactorsR" recursive method, but I'm kind of confuse

    public class Tester {     
     
        static boolean isPrime(int p)
        {
            for(int i = 2; i < p; i++)
            {
                if(p % i == 0) return false;
            }
            return true;
        }
     
     
     
       public static void primeFactors(int n)
       {
           primeFactorsR(n, n-1);
       }
     
       public static void primeFactorsR(int n, int m)
       {
           if(isPrime(n))
               System.out.println(n);
           else
               if(n % m == 0)
               {
                   primeFactorsR(m, m-1);
                   primeFactorsR(n/m, (n/m)-1);              
               }
               else
                   primeFactorsR(n, m-1);
       }
     
     
     
     
        public static void main(String[] args) {  
     
     
               primeFactors(20);
     
     
     
        }
    }

    Thanks


  2. #2
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: how to trace recursion variables in a recursive method

    Try adding println's.

        public class Tester {     
     
          static boolean isPrime(int p)
          {
             for(int i = 2; i < p; i++)
             {
                if(p % i == 0) 
                   return false;
             }
             return true;
          }
     
     
     
          public static void primeFactors(int n)
          {
             primeFactorsR(n, n-1);
          }
     
          public static void primeFactorsR(int n, int m)
          {
             if(isPrime(n))
                System.out.println(n);
             else
                if(n % m == 0)
                {
                   System.out.println("n " + n + " m " + m);
                   System.out.println("m " + m + " m-1 " + (m-1));
                   primeFactorsR(m, m-1);
     
                   System.out.println("n/m " + (n/m) + " (n/m) -1 " + (n/m - 1));
                   primeFactorsR(n/m, (n/m)-1);              
                }
                else
                {
                   System.out.println("n " + n + " m " + m);
                   System.out.println("n " + n + " m - 1 " + ( m-1));
                   primeFactorsR(n, m-1);
                }
          }
     
     
     
     
          public static void main(String[] args) {  
     
     
             primeFactors(20);
     
     
     
          }
       }

     

    n 20 m 19
    n 20 m - 1 18
    n 20 m 18
    n 20 m - 1 17
    n 20 m 17
    n 20 m - 1 16
    n 20 m 16
    n 20 m - 1 15
    n 20 m 15
    n 20 m - 1 14
    n 20 m 14
    n 20 m - 1 13
    n 20 m 13
    n 20 m - 1 12
    n 20 m 12
    n 20 m - 1 11
    n 20 m 11
    n 20 m - 1 10
    n 20 m 10
    m 10 m-1 9
    n 10 m 9
    n 10 m - 1 8
    n 10 m 8
    n 10 m - 1 7
    n 10 m 7
    n 10 m - 1 6
    n 10 m 6
    n 10 m - 1 5
    n 10 m 5
    m 5 m-1 4
    5
    n/m 2 (n/m) -1 1
    2
    n/m 2 (n/m) -1 1
    2




    Last edited by javapenguin; May 21st, 2012 at 07:54 PM.

  3. #3
    Member
    Join Date
    Mar 2009
    Posts
    91
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: how to trace recursion variables in a recursive method

    yes, I did that, but I'm having problem knowing when this call "primeFactorsR(n/m, (n/m)-1)" takes place.
    ones it gets here "primeFactorsR(m, m-1)" it will enter the next recursion or it will continue to "primeFactorsR(n/m, (n/m)-1)"

    another thing lets say recursion get to 10 and 5, then it enter this part

    if(n % m == 0)
                {
                   System.out.println("n " + n + " m " + m);
                   primeFactorsR(m, m-1);
                   primeFactorsR(n/m, (n/m)-1);              
                }

    now the next recursion is primeFactorsR(5, 4)

    next iteration prints 5 to screeen because is prime, and exits the loop... am I wrong here?
    Last edited by mia_tech; May 21st, 2012 at 08:10 PM.

  4. #4
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: how to trace recursion variables in a recursive method

    As It will be calling

    primeFactorsR(m, m-1);
    primeFactorsR(n/m, (n/m)-1);

    And will call

    primeFactorsR(m, m-1);

    until it is done, before going to
    primeFactorsR(n/m, (n/m)-1);

    Have a class variable and make it be 0 and add 1 to it every time the method is called before it goes to

    primeFactorsR(n/m, (n/m)-1);

    for the first time.


       public class Tester {     
          private static int count = 0;
     
          static boolean isPrime(int p)
          {
             for(int i = 2; i < p; i++)
             {
                if(p % i == 0) 
                   return false;
             }
             return true;
          }
     
     
     
          public static void primeFactors(int n)
          {
             primeFactorsR(n, n-1);
          }
     
          public static void primeFactorsR(int n, int m)
          {
             count++;
             if(isPrime(n))
                System.out.println(n);
             else
                if(n % m == 0)
                {
                   System.out.println("n " + n + " m " + m);
                   System.out.println("m " + m + " m-1 " + (m-1));
                   primeFactorsR(m, m-1);
     
                   System.out.println("n/m " + (n/m) + " (n/m) -1 " + (n/m - 1));
                   System.out.println("Count: " + count);
                   primeFactorsR(n/m, (n/m)-1);              
                }
                else
                {
                   System.out.println("n " + n + " m " + m);
                   System.out.println("n " + n + " m - 1 " + ( m-1));
                   primeFactorsR(n, m-1);
                }
          }
     
     
     
     
          public static void main(String[] args) {  
     
     
             primeFactors(20);
     
     
     
          }
       }

     

    n 20 m 19
    n 20 m - 1 18
    n 20 m 18
    n 20 m - 1 17
    n 20 m 17
    n 20 m - 1 16
    n 20 m 16
    n 20 m - 1 15
    n 20 m 15
    n 20 m - 1 14
    n 20 m 14
    n 20 m - 1 13
    n 20 m 13
    n 20 m - 1 12
    n 20 m 12
    n 20 m - 1 11
    n 20 m 11
    n 20 m - 1 10
    n 20 m 10
    m 10 m-1 9
    n 10 m 9
    n 10 m - 1 8
    n 10 m 8
    n 10 m - 1 7
    n 10 m 7
    n 10 m - 1 6
    n 10 m 6
    n 10 m - 1 5
    n 10 m 5
    m 5 m-1 4
    5
    n/m 2 (n/m) -1 1
    Count: 16
    2
    n/m 2 (n/m) -1 1
    Count: 17
    2




    It appears that after the 16th method call, it goes to there and goes there once more again at the 17th.

  5. #5
    Member
    Join Date
    Mar 2009
    Posts
    91
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: how to trace recursion variables in a recursive method

    ok, I'm almost there... but why when it reaches 5 and 4 skips this part

    System.out.println("n " + n + " m " + m);
    System.out.println("m " + m + " m-1 " + (m-1));
    primeFactorsR(m, m-1);

    and goes straight to
    System.out.println("n/m " + (n/m) + " (n/m) -1 " + (n/m - 1));
    System.out.println("Count: " + count1++);
    primeFactorsR(n/m, (n/m)-1);

  6. #6
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: how to trace recursion variables in a recursive method

    Quote Originally Posted by mia_tech View Post
    yes, I did that, but I'm having problem knowing when this call "primeFactorsR(n/m, (n/m)-1)" takes place.
    ones it gets here "primeFactorsR(m, m-1)" it will enter the next recursion or it will continue to "primeFactorsR(n/m, (n/m)-1)"

    another thing lets say recursion get to 10 and 5, then it enter this part

    if(n % m == 0)
                {
                   System.out.println("n " + n + " m " + m);
                   primeFactorsR(m, m-1);
                   primeFactorsR(n/m, (n/m)-1);              
                }

    now the next recursion is primeFactorsR(5, 4)

    next iteration prints 5 to screeen because is prime, and exits the loop... am I wrong here?
    That would depend if there were any more cases left, as you're still calling the method.

    It would have to go through all calls that might be entailed with

    primeFactorsR(n/m, (n/m)-1);

    before exiting the loop, at least I think so.

    It later prints out

    2
    2

    so it can't be done after 5.

    Every time it makes a method call, assume that it goes back to the first line of the method, with the new values as its params. Hence it will only exit the method, unless something goes wrong like an exception or something, or if it were to go into an infinite loop, when it is done with all method calls.

  7. The Following User Says Thank You to javapenguin For This Useful Post:

    mia_tech (May 21st, 2012)

  8. #7
    Member
    Join Date
    Mar 2009
    Posts
    91
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: how to trace recursion variables in a recursive method

    if n = 5 it enters the first if prints the number and it would exit the recursion, I still don't see how would print the 2's

  9. #8
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: how to trace recursion variables in a recursive method

    Quote Originally Posted by mia_tech View Post
    ok, I'm almost there... but why when it reaches 5 and 4 skips this part

    System.out.println("n " + n + " m " + m);
    System.out.println("m " + m + " m-1 " + (m-1));
    primeFactorsR(m, m-1);

    and goes straight to
    System.out.println("n/m " + (n/m) + " (n/m) -1 " + (n/m - 1));
    System.out.println("Count: " + count1++);
    primeFactorsR(n/m, (n/m)-1);
    Once it hits 5, it then goes to finish off the other recursive calls left over.

    For each of the recursive calls it had before it hit 5, it still has to call the second half that it had been ignoring.

    It still has to deal with the second statement as it goes in call order dealiing with the recursive calls until it hits the println before going to that second one.

  10. #9
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: how to trace recursion variables in a recursive method

    Quote Originally Posted by mia_tech View Post
    if n = 5 it enters the first if prints the number and it would exit the recursion, I still don't see how would print the 2's
    Treat each new call to primeFactorsR as starting at the beginning each time.

    It could either go to the if, in which case it would stop recursively calling the method.
    It could go to the else if
    it would go to the first statement in the else if and recursively call till it hit the first case. Then it would go to the second statement in the else if

    If it didn't go to the if or the else if, then it would go to the else and recursively call till it hit the first case (the if part)

    The if part is what's called a base case. It guarantees, or is meant to guarantee, that the recursive calls won't go on forever.

  11. #10
    Member
    Join Date
    Mar 2009
    Posts
    91
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: how to trace recursion variables in a recursive method

    Quote Originally Posted by javapenguin View Post
    Treat each new call to primeFactorsR as starting at the beginning each time.

    It could either go to the if, in which case it would stop recursively calling the method.
    It could go to the else if
    it would go to the first statement in the else if and recursively call till it hit the first case. Then it would go to the second statement in the else if

    If it didn't go to the if or the else if, then it would go to the else and recursively call till it hit the first case (the if part)

    The if part is what's called a base case. It guarantees, or is meant to guarantee, that the recursive calls won't go on forever.
    look at the code there's not "else if"... there's a nested "if, else" statement. So what you're telling me is that once (n % m == 0) it calls these two recursive method before starting all over again?

    primeFactorsR(m, m-1);
    primeFactorsR(n/m, (n/m)-1);

  12. #11
    Member
    Join Date
    Mar 2009
    Posts
    91
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: how to trace recursion variables in a recursive method

    ok, I narrowed down, and now I know which part is that I don't understand. I modified the method a bit, so bare with me. Take a look at the output and explain why when n = 5 it prints 5; however, right after that n goes back to be n = 10, and the 3rd method executes bypassing the second method

    public static void primeFactorsR(int n, int m)
          {
             if(isPrime(n))
             {
                 System.out.println(n);
                 System.out.println("method1 " +count1++);
             }     
             else
                if(n % m == 0)
                {
                   System.out.println("n " + n + " m " + m);
                   System.out.println("method2: " + count2++);
                   primeFactorsR(m, m-1);
     
                   System.out.println("n " + n + " m " + m);
                   System.out.println("method3: " + count3++);
                   primeFactorsR(n/m, (n/m)-1);              
                }
                else
                {
                   System.out.println("n " + n + " m " + m);
                   //System.out.println("n " + n + " m - 1 " + ( m-1));
                   System.out.println("method4: " + count4++);
                   primeFactorsR(n, m-1);
                }
          }

    output

    n 20 m 19
    method4: 1
    n 20 m 18
    method4: 2
    n 20 m 17
    method4: 3
    n 20 m 16
    method4: 4
    n 20 m 15
    method4: 5
    n 20 m 14
    method4: 6
    n 20 m 13
    method4: 7
    n 20 m 12
    method4: 8
    n 20 m 11
    method4: 9
    n 20 m 10
    method2: 1
    n 10 m 9
    method4: 10
    n 10 m 8
    method4: 11
    n 10 m 7
    method4: 12
    n 10 m 6
    method4: 13
    n 10 m 5
    method2: 2
    5
    method1 1
    n 10 m 5
    method3: 1
    2
    method1 2
    n 20 m 10
    method3: 2
    2
    method1 3

  13. #12
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,607
    Thanks
    24
    Thanked 315 Times in 295 Posts

    Default Re: how to trace recursion variables in a recursive method

    I assume you are talking about this bit:
    n 10 m 5
    method2: 2
    5
    method1 1
    n 10 m 5
    method3: 1
    2
    method1 2
    n 20 m 10
    method3: 2
    2
    method1 3

    The second method is not exactly being "bypassed". Consider that immediately after method2 prints out, it calls the primeFactorsR(m,m-1) method. The method is executed recursively, and it is sent the variables n=5 and m=4. 5 is a prime number, so method1 print outs. After method1 prints out, it then returns from the method.
    But, and I believe this is where you are confused, where does it return TO? Well, it returns to where you called the primeFactorsR(m,m-1) method, immediately after printing out method2. So it then continues with the code, and the code tells it to print out method3, and then call the primeFactorsR(n/m,(n/m)-1) method. I'll try to think of a way to print out the data that may make it easier for you to see the recursion happening.
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  14. #13
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,607
    Thanks
    24
    Thanked 315 Times in 295 Posts

    Default Re: how to trace recursion variables in a recursive method

    For the sake of getting a better understanding of recursion, compile and run this code:
    public class recursiontests {
     
    	static int count1;
    	static int count2;
    	static int count3;
    	static int count4;
     
    	public static void primeFactors(int n)
    	{
    	       primeFactorsR(n, n-1,0);
    	}
     
    	public static boolean isPrime(int p)
        {
            for(int i = 2; i < p; i++)
            {
                if(p % i == 0) return false;
            }
            return true;
        }
     
    	public static void primeFactorsR(int n,int m,int rec) {
    		String indent = "";
    		for(int i=0;i<rec;i++)
    			indent+="|";
    		if(isPrime(n))
    	    {
    	    	System.out.println(indent+n);
    	    	System.out.println(indent+"method1 " +count1++);
    	    }     
    	    else if(n % m == 0)
    	    {
    	    	System.out.println(indent+"n " + n + " m " + m);
    	    	System.out.println(indent+"method2: " + count2++);
    	    	primeFactorsR(m, m-1, rec+1);
    	    	if(rec!=0)
    	    		System.out.println(indent);
     
    	    	System.out.println(indent+"n " + n + " m " + m);
    	        System.out.println(indent+"method3: " + count3++);
    	        primeFactorsR(n/m, (n/m)-1, rec+1);   
    	        if(rec!=0)
    	    		System.out.println(indent);
    	     }
    	     else
    	     {
    	     	System.out.println(indent+"n " + n + " m " + m);
    	        System.out.println(indent+"method4: " + count4++);
    	        primeFactorsR(n, m-1, rec+1);
    	        if(rec!=0)
    	    		System.out.println(indent);
    	     }
    	}
     
    	public static void main(String[] args) {
    		primeFactors(20);
    	}
    }

    It should produce an output similar to this:
    n 20 m 19
    method4: 0
    |n 20 m 18
    |method4: 1
    ||n 20 m 17
    ||method4: 2
    |||n 20 m 16
    |||method4: 3
    ||||n 20 m 15
    ||||method4: 4
    |||||n 20 m 14
    |||||method4: 5
    ||||||n 20 m 13
    ||||||method4: 6
    |||||||n 20 m 12
    |||||||method4: 7
    ||||||||n 20 m 11
    ||||||||method4: 8
    |||||||||n 20 m 10
    |||||||||method2: 0
    ||||||||||n 10 m 9
    ||||||||||method4: 9
    |||||||||||n 10 m 8
    |||||||||||method4: 10
    ||||||||||||n 10 m 7
    ||||||||||||method4: 11
    |||||||||||||n 10 m 6
    |||||||||||||method4: 12
    ||||||||||||||n 10 m 5
    ||||||||||||||method2: 1
    |||||||||||||||5
    |||||||||||||||method1 0
    ||||||||||||||
    ||||||||||||||n 10 m 5
    ||||||||||||||method3: 0
    |||||||||||||||2
    |||||||||||||||method1 1
    ||||||||||||||
    |||||||||||||
    ||||||||||||
    |||||||||||
    ||||||||||
    |||||||||
    |||||||||n 20 m 10
    |||||||||method3: 1
    ||||||||||2
    ||||||||||method1 2
    |||||||||
    ||||||||
    |||||||
    ||||||
    |||||
    ||||
    |||
    ||
    |

    It is the same code as what you had (for the most part, I gave it a different name), but I added something to the output to make the levels of recursion more visible. Each | represents one level deep of recursion. Every time a line is one level deeper than the previous line, it means the method was called recursively, and each time a line is one level less than the previous line, it means it has returned from where the method was called recursively.
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

Similar Threads

  1. Problem with recursive method. Can you help?
    By TFLeGacY in forum Algorithms & Recursion
    Replies: 6
    Last Post: December 7th, 2011, 04:44 PM
  2. Problem with fairly basic recursive method
    By TFLeGacY in forum Algorithms & Recursion
    Replies: 2
    Last Post: December 6th, 2011, 08:58 PM
  3. How do I connect 2 method headers to make it recursive???
    By tripline in forum What's Wrong With My Code?
    Replies: 1
    Last Post: November 5th, 2011, 05:27 AM
  4. Recursion Trace
    By hello_world in forum Algorithms & Recursion
    Replies: 4
    Last Post: August 22nd, 2011, 10:35 PM
  5. [SOLVED] StackOverflowError with recursive method
    By samfin in forum What's Wrong With My Code?
    Replies: 4
    Last Post: December 2nd, 2010, 03:05 PM