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
Code :
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
Re: how to trace recursion variables in a recursive method
Try adding println's.
Code java:
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
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
Code :
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?
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.
Code java:
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.
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
Code :
System.out.println("n " + n + " m " + m);
System.out.println("m " + m + " m-1 " + (m-1));
primeFactorsR(m, m-1);
and goes straight to
Code :
System.out.println("n/m " + (n/m) + " (n/m) -1 " + (n/m - 1));
System.out.println("Count: " + count1++);
primeFactorsR(n/m, (n/m)-1);
Re: how to trace recursion variables in a recursive method
Quote:
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
Code :
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.
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
Re: how to trace recursion variables in a recursive method
Quote:
Originally Posted by
mia_tech
ok, I'm almost there... but why when it reaches 5 and 4 skips this part
Code :
System.out.println("n " + n + " m " + m);
System.out.println("m " + m + " m-1 " + (m-1));
primeFactorsR(m, m-1);
and goes straight to
Code :
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.
Re: how to trace recursion variables in a recursive method
Quote:
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.
Re: how to trace recursion variables in a recursive method
Quote:
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?
Code :
primeFactorsR(m, m-1);
primeFactorsR(n/m, (n/m)-1);
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
Code :
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
Code :
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
Re: how to trace recursion variables in a recursive method
I assume you are talking about this bit:
Code :
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.
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:
Code java:
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:
Code :
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.
