Hello,

I know this question might sound stupid!
I am using recursion inside a loop. I want to stop the loop as soon as the method is called recursively and resume it again when the call returns. I am not able to do so. Do I need to lock the method?

Here is my code:

public class Max2Friends {
    String[] f = {"NYNNN", "YNYNN", "NYNYN", "NNYNY", "NNNYN"};
    int[] twof = {0, 0, 0, 0, 0};

    public static void main(String[] args) {
        Max2Friends obj=new Max2Friends();   
        obj.Calculate(999,999);
    } 

    public void Calculate(int p, int t) {
        System.out.println("p=" + p);
        System.out.println("t=" + t);

        for (int i = 0; i != p && i < 5; i++) {
            System.out.println("i=" + i);
            System.out.println("p value inside=" + p);
            System.out.println("t value inside=" + t);

            if (i == t)
                i=i+1;

            for (int j = 0; j < 5; j++) {
                if (f[i].charAt(j) == 'Y' && p == 999) {
                    Calculate(i,j);
                } else if (f[i].charAt(j) == 'Y' && j == t) {
                    twof[p]++;
                    break;
                }
            }
        }
    }
}

The p and t values outside and inside the for loops are different. I want the loops to stop executing as soon as the function is called recursively.I want the recursion to complete and then resume the loops.What seems to be happening is that both are taking place simultaneously due to which I am getting different values for p and t inside and outside the loops.

I am using recursion inside a loop. I want to stop the loop as soon as the method is called recursively and resume it again when the call returns

At first blush, this sounds like a strange thing to want. I'm not sure I really understand what you mean. Do you mean that you want to turn off the loop for any recursive call of the method, or that you want to stop the current loop when you make the recursive call?

I'll look at the code a little, maybe it'll become clear.

Do you mean that you want to turn off the loop for any recursive call of the method, or that you want to stop the current loop when you make the recursive call?

I'll look at the code a little, maybe it'll become clear.

Yes,I want the loops(both outer as well as inner) to pause once the recursive call is made,let the recursive function execute and when it returns then let the loop resume.

I was assuming that that will be the default behavior but it doesn't seem to be the case.

I'm starting to understand it - recursion always requires a bit of work for me, but I think I'm getting it.

I put in some debugging code that might help you see what's going on.

Try this: declare a field

private static int recurseCounter;

and set it to 0 in your main.

Then declare an int localCounter within Calculate, and assign it like so, first line of Calculate:

int localCounter = Max2Friends.recurseCounter ++;

Now you have an index to tell you how deep you are in the recursion stack. Append that to the printouts of your variables, so you can see where you are, like so:

java Max2Friends
----------------------------------
Entering Recursion # 0
----------------------------------
p=999
t=999
i=0
p value inside call# 0=999
t value inside call# 0=999
----------------------------------
Entering Recursion # 1
----------------------------------
p=0
t=1
----------------------------------
Exiting Recursion # 1
----------------------------------
i=1
p value inside call# 0=999
t value inside call# 0=999
----------------------------------
Entering Recursion # 2
----------------------------------
p=1
t=0
i=0
p value inside call# 2=1
t value inside call# 2=0
i=2
p value inside call# 2=1
t value inside call# 2=0
i=3
p value inside call# 2=1
t value inside call# 2=0
i=4
p value inside call# 2=1
t value inside call# 2=0
----------------------------------
Exiting Recursion # 2
----------------------------------
----------------------------------
Entering Recursion # 3
----------------------------------
p=1
t=2
i=0
p value inside call# 3=1
t value inside call# 3=2
----------------------------------
Exiting Recursion # 3
----------------------------------
(output continues...)


So the odd thing about this is that you have a sort of serial recursion. Rather than nesting, your recursive calls seem to come in sequence, with one exiting before the next begins. This is not standard recursive behavior.

More later...

Edited 6 Years Ago by jon.kiparsky: n/a

I want the loops to stop executing as soon as the function is called recursively.

Try breaking out of the loops immediately after the recursive call is made.

I don't think I understand what is going on.p and t values inside call#1 are not getting printed at all and when recursion starts at call#1 the following values get printed again.

p value inside call# 0 is: 999
t value inside call# 0 is: 999

Try breaking out of the loops immediately after the recursive call is made.

I will not be able to resume my loop if I break out of it.

I want to stop the loop as soon as the method is called recursively and resume it again when the call returns

The loop will be stopped until the called method returns. That would be the normal way the code works.
Can you rephrase your question.

What is the code supposed to do? What should the output look like?

Edited 6 Years Ago by NormR1: n/a

I don't think I understand what is going on.p and t values inside call#1 are not getting printed at all and when recursion starts at call#1 the following values get printed again.

p value inside call# 0 is: 999
t value inside call# 0 is: 999

Yes - and if you put in this checking language and run it locally you'll see that this happens again. You might want to make yourself into the compiler and run through it step by step. Have a piece of paper handy to keep track of where you are.
(You sometimes have to do this with recursion, if it goes haywire)

The loop will be stopped until the called method returns. That would be the normal way the code works.
Can you rephrase your question.

What is the code supposed to do? What should the output look like?

How will the loop resume if I break out of it? When the call returns,if the next statement to be executed is a break then the control will go out of the loop.

The code is supposed to find the number of two friends each person has. If two people A and B have a common friend C then A and B are two friends with each other.The character Y in f array indicates that the two people are friends with each other and N indicates they are not.

Yes - and if you put in this checking language and run it locally you'll see that this happens again. You might want to make yourself into the compiler and run through it step by step. Have a piece of paper handy to keep track of where you are.
(You sometimes have to do this with recursion, if it goes haywire)

I'll give it a try.

The character Y in f array indicates that the two people are friends with each other and N indicates they are not.

How are the 5 entries in the array related? What is the index into the array for person one and person two that you get the answer Y or N?

Can you explain the array f and how it relates to two persons?

What is the answer/solution supposed to be???

Other questions about the code:
Is the hardcoded 5 the length of f?
Is the hardcoded 999 passed as the first args to Calculate have the same sematic meaning as the 999 used in the if test?

How are the 5 entries in the array related? What is the index into the array for person one and person two that you get the answer Y or N?

Can you explain the array f and how it relates to two persons?

What is the answer/solution supposed to be???

Other questions about the code:
Is the hardcoded 5 the length of f?
Is the hardcoded 999 passed as the first args to Calculate have the same sematic meaning as the 999 used in the if test?

String[] f = {"NYNNN", "YNYNN", "NYNYN", "NNYNY", "NNNYN"};

f[0]="NYNNN";

This indicates that the person 0 is friends only with person 1.This also indicates that he/she is 2-Friends with person 2 since they both have person 1 as a common friend.So,in the above case all the people have just 1 2-Friend except for Person 2 who has two 2-friends.

The answer varies with the input given.Right now I have hard coded the length of f to test with a particular input.

I do not know what semantic meaning does 999 have in the if test.

Try tracing what your code is actually doing. I think you might change your mind about what the issue is.

I assume "the number of two friends" is the number of second-degree friends, that is, the number of friends of friends who are not themselves friends? If I am a friend of Norm and of Tong, and Norm and Tong are friends of each other and of James, how many second-degree friends (two-friends) do I have?

semantic meaning does 999 have in the if test.

The meaning is that the if tests for the first call to the method (ie at top level).

The answer varies with the input given

What is the answer for the GIVEN INPUT?

I've rewritten your code and given it some more meaningful names.
Do I understand it correctly? It only recurs one level?

public class RecursionProblem {
    final String[] NandY = {"NYNNN", 
                            "YNYNN", 
                            "NYNYN", 
                            "NNYNY", 
                            "NNNYN"};

    int[] twof = {0, 0, 0, 0, 0};  // count here

    final static int NbrLoops = 999;

    static int recLvl = 0;

    //--------------------------------------------
    public static void main(String[] args) {
        RecursionProblem obj = new RecursionProblem();   
        obj.Calculate(NbrLoops, NbrLoops);
        System.out.println("twof=" + java.util.Arrays.toString(obj.twof));
        //twof=[0, 1, 2, 2, 2]
    } 


    public void Calculate(final int elmIdx, final int tIdx) {
        System.out.println("Starting: elmIdx=" + elmIdx + ",  tIdx=" + tIdx + ", recLvl=" + recLvl);

        for (int nxtElm = 0; nxtElm != elmIdx && nxtElm < NandY.length; nxtElm++) {
            System.out.println(" >>In loop  nxtElm=" + nxtElm + ",  elmIdx=" + elmIdx + ", tIdx=" + tIdx);

            if (nxtElm == tIdx) { // What is this test for???
                nxtElm = nxtElm+1;
                System.out.println("nxtElm bumped to " + nxtElm + " when tIdx=" + tIdx);
            }

            for (int chrIdx = 0; chrIdx < NandY[nxtElm].length(); chrIdx++) {
                if (NandY[nxtElm].charAt(chrIdx) == 'Y' && elmIdx == NbrLoops) { // At top level only
                    recLvl++;  // add one going down
                    Calculate(nxtElm, chrIdx);
                    recLvl--;  // restore to previous value

                } else if (NandY[nxtElm].charAt(chrIdx) == 'Y' && chrIdx == tIdx) {
                    twof[elmIdx]++;      // count the friends
                    System.out.println(".>>>friend for nxtElm=" + nxtElm + ", chrIdx=" + chrIdx + ",  elmIdx=" + elmIdx);
                    break;   

                }else {
                  System.out.println("NandY not Y  nxtElm=" + nxtElm + ", chrIdx=" + chrIdx);
                }
            } // end for(chrIdx)
        } // end for(nxtElm)
    } // end Calculate()

}  // end class

Edited 6 Years Ago by NormR1: n/a

Try tracing what your code is actually doing. I think you might change your mind about what the issue is.

I assume "the number of two friends" is the number of second-degree friends, that is, the number of friends of friends who are not themselves friends? If I am a friend of Norm and of Tong, and Norm and Tong are friends of each other and of James, how many second-degree friends (two-friends) do I have?

One.

The meaning is that the if tests for the first call to the method (ie at top level).


What is the answer for the GIVEN INPUT?

I've rewritten your code and given it some more meaningful names.
Do I understand it correctly? It only recurs one level?

public class RecursionProblem {
    final String[] NandY = {"NYNNN", 
                            "YNYNN", 
                            "NYNYN", 
                            "NNYNY", 
                            "NNNYN"};

    int[] twof = {0, 0, 0, 0, 0};  // count here

    final static int NbrLoops = 999;

    static int recLvl = 0;

    //--------------------------------------------
    public static void main(String[] args) {
        RecursionProblem obj = new RecursionProblem();   
        obj.Calculate(NbrLoops, NbrLoops);
        System.out.println("twof=" + java.util.Arrays.toString(obj.twof));
        //twof=[0, 1, 2, 2, 2]
    } 


    public void Calculate(final int elmIdx, final int tIdx) {
        System.out.println("Starting: elmIdx=" + elmIdx + ",  tIdx=" + tIdx + ", recLvl=" + recLvl);

        for (int nxtElm = 0; nxtElm != elmIdx && nxtElm < NandY.length; nxtElm++) {
            System.out.println(" >>In loop  nxtElm=" + nxtElm + ",  elmIdx=" + elmIdx + ", tIdx=" + tIdx);

            if (nxtElm == tIdx) { // What is this test for???
                nxtElm = nxtElm+1;
                System.out.println("nxtElm bumped to " + nxtElm + " when tIdx=" + tIdx);
            }

            for (int chrIdx = 0; chrIdx < NandY[nxtElm].length(); chrIdx++) {
                if (NandY[nxtElm].charAt(chrIdx) == 'Y' && elmIdx == NbrLoops) { // At top level only
                    recLvl++;  // add one going down
                    Calculate(nxtElm, chrIdx);
                    recLvl--;  // restore to previous value

                } else if (NandY[nxtElm].charAt(chrIdx) == 'Y' && chrIdx == tIdx) {
                    twof[elmIdx]++;      // count the friends
                    System.out.println(".>>>friend for nxtElm=" + nxtElm + ", chrIdx=" + chrIdx + ",  elmIdx=" + elmIdx);
                    break;   

                }else {
                  System.out.println("NandY not Y  nxtElm=" + nxtElm + ", chrIdx=" + chrIdx);
                }
            } // end for(chrIdx)
        } // end for(nxtElm)
    } // end Calculate()

}  // end class

In the current case all the people have just one 2-Friend except for Person 2 who has two 2-friends.

Yes,you have understood my code correctly.

The test "if (nxtElm == tIdx)" is for checking whether the two indices are same or not.A person can't be friend with himself/herself so I increment the counter such that the friends of the next person are checked.

Why do you use recursion? I only see the program calling itself one time when it has been called initially. It doesn't go deeper than one level.

Edited 6 Years Ago by NormR1: n/a

Why do you use recursion? I only see the program calling itself one time when it has been called initially. It doesn't go deeper than one level.

Calculate(nxtElm, chrIdx);

The function is being recursively called here.

It only goes down one level because it won't make any further calls because of the if test for the initial value of the arg being 999 or whatever.

Also how can the value of twof[] be incremented for person 0? The t value has the 999 value?

Edited 6 Years Ago by NormR1: n/a

I think I understand why you were going with a recursive solution. Right now you're only looking for 2nd degree friends, but if you wanted to search deeper, you would do it recursively, right? So searching for 4th-degree friends, you'd end up going four calls deep in the stack?

I think I start to see the logic here. Depending on the data set, this might be an expensive procedure.

It only goes down one level because it won't make any further calls because of the if test for the initial value of the arg being 999 or whatever.

Also how can the value of twof[] be incremented for person 0? The t value has the 999 value?

Yes,it goes down only one level but for each 'Y' value in the NandY(friend) array.

The elmIdx value will be changing when the function is recursively called.The first recursive call will result in Calculate(0,1) being called and for nxtElm=2,chrIdx=1 the chrIdx and tIdx values will be the same and twof[elmIdx],where elmIdx is 0 will get incremented.So,twof[0] gets incremented. This is what my understanding is.Let me know where I am going wrong.

Edited 6 Years Ago by ChPravin: n/a

where I am going wrong.

To solve a logic error like this one, you need to take a piece of paper and a pencil and play computer. Step thru the program step by step until you see where the logic is wrong.

You've had a week to be playing with this. Maybe you can give us an idea of where you're at now - what does the code look like now, what have you learned, and what are your current issues?

This article has been dead for over six months. Start a new discussion instead.