Thread: 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

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.

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);

Originally Posted by mia_tech

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.

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

Originally Posted by mia_tech

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.

Originally Posted by mia_tech

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.

Originally Posted by javapenguin

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);

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