13 Replies Latest reply: Feb 8, 2011 1:48 PM by 796440 RSS

    mutual recursion without threading

    801092
      Hello,

      I have a question, how can one do mutual recursion without using threading?

      What I am trying to do is have the following:

      Function 1
      Function 2
      Function 1
      Function 2

      Meaning that the function alternate between the other.

      I'm not looking for code, possibly pointing to the right direction, I've looked online and have not seen this type of mutual recursion.

      Thank you in advance.
        • 1. Re: mutual recursion without threading
          EJP
          I have a question, how can one do mutual recursion without using threading?
          Do you mean co-routining? You can't do it in Java. You can't do that without language support. Essentially you need an instruction to swap the top of the stack with the PC. Maybe there is some Java library out there that does it. I haven't used co-routining since 1979 myself ...
          • 2. Re: mutual recursion without threading
            801092
            EJP (and anyone else),

            Yes, I guess what I want to do is coroutining, but I can't use threads.

            Basically, I want to have two routines alternate between each other.

            Example:
            Function 1
            Function 2
            Function 1
            Function 2
            etc...
            • 3. Re: mutual recursion without threading
              gimbal2
              So? Create a loop and call the methods alternating.
              for(int i = 0; i < whatever; i++){
                method1();
                method2();
              }
              • 4. Re: mutual recursion without threading
                EJP
                Assuming he wants co-routining, that isn't it.
                • 5. Re: mutual recursion without threading
                  gimbal2
                  I don't focus on what he wants; I focus on the results. Given the previous post, that is it.
                  • 6. Re: mutual recursion without threading
                    YoungWinston
                    798089 wrote:
                    Basically, I want to have two routines alternate between each other.
                    I think we need a bit more detail. Why do you need this? Do they need to run "in parallel" (difficult, without threading)? Do state changes in one function affect the behaviour of the other? In the absence of anything further to go on, gimbal's suggestion sounds like the best.

                    Winston
                    • 7. Re: mutual recursion without threading
                      EJP
                      I don't focus on what he wants; I focus on the results. Given the previous post, that is it.
                      Only if you don't know what co-routining is.
                      • 8. Re: mutual recursion without threading
                        801092
                        YoungWinston,

                        Sorry for not being detailed enough.

                        The functions affect each other. Meaning that function1 is called, and the value of function1 is read into function2, and they alternate. These functions do not run in parallel, but rather alternate between the two.

                        Hope this helps.
                        • 9. Re: mutual recursion without threading
                          EJP
                          Did you try Google? I found this top of the list.
                          • 10. Re: mutual recursion without threading
                            796440
                            798089 wrote:
                            YoungWinston,

                            Sorry for not being detailed enough.

                            The functions affect each other. Meaning that function1 is called, and the value of function1 is read into function2, and they alternate. These functions do not run in parallel, but rather alternate between the two.

                            Hope this helps.
                            I might be totally off base here, but it doesn't sound like you're asking about co-routining. It sounds like simple sequential coding, that happens to be recursive.
                            int method1(int i) {
                              if (terminal condition) {
                                return something;
                              }
                              else {
                                i2 = some subset of the problem derived from i;
                                return method2(i2);
                              }
                            }
                            
                            int method2(int i) {
                              if (terminal condition) {
                                return somethign;
                              }
                              else {
                                i2 = some subset of the problem derived from i;
                                return method1(i2);
                              }
                            }
                            So, assuming I'm missing something here, what am I missing here?
                            • 11. Re: mutual recursion without threading
                              796440
                              798089 wrote:
                              YoungWinston,

                              Sorry for not being detailed enough.

                              The functions affect each other. Meaning that function1 is called, and the value of function1 is read into function2, and they alternate. These functions do not run in parallel, but rather alternate between the two.

                              Hope this helps.
                              If it really is as simple as you make it sound--just 2 methods recursively calling each other, not co-routining--then here's a real-world example, although slightly more complex, to calculate the [url http://en.wikipedia.org/wiki/Ackerman_function]Ackerman Function.

                              If I'm wrong, and you do need co-routining, I'd be interested to hear a little about why, about what you're trying to accomplish with it, and why you can't use multiple threads.

                              I guess if you need the two to alternate indefinitely, without blowing the stack, then that's where co-routines would work and recursion wouldn't. But again, why no multithreading?
                              package scratch;
                              
                              public class Ackerman {
                                public static void main (String[] args) throws Exception {
                                  for (long m : new long[] {0, 1, 2, 3}) {
                                    for (long n : new long[] {0, 1, 2, 3, 4, 5, 6, 9}) {
                                      System.out.printf ("A(%d, %d) = %d%n", m, n, ack(m,n));
                                    }
                                    System.out.println ();
                                  }
                                }
                              
                                public static long ack(long m, long n) {
                                  if (m == 0) {
                                    return n + 1;
                                  }
                                  else if (n == 0) {
                                    return ack2(m);
                                  }
                                  else {
                                    return ack3(m, n);
                                  }
                                }
                              
                                private static long ack2(long m) {
                                  return ack(m - 1, 1);
                                }
                              
                                private static long ack3(long m, long n) {
                                  return ack(m - 1, ack (m, n - 1));
                                }
                              }
                              Edited by: jverd on Feb 7, 2011 10:13 PM
                              • 12. Re: mutual recursion without threading
                                YoungWinston
                                jverd wrote:
                                ...here's a real-world example, although slightly more complex, to calculate the [url http://en.wikipedia.org/wiki/Ackerman_function]Ackerman Function.
                                Blimey. There's a blast from the past! I haven't seen ack() for years. I think I might implement it using BigInteger though :-).

                                Winston
                                • 13. Re: mutual recursion without threading
                                  796440
                                  YoungWinston wrote:
                                  jverd wrote:
                                  ...here's a real-world example, although slightly more complex, to calculate the [url http://en.wikipedia.org/wiki/Ackerman_function]Ackerman Function.
                                  Blimey. There's a blast from the past! I haven't seen ack() for years. I think I might implement it using BigInteger though :-).
                                  Initially I did use BI, but I blew out my stack long before I got anywhere near even int's upper bound.

                                  http://xkcd.com/207/ Third panel. (On an unrelated note, I used to do panel #1 in real life every time I dropped my kids off for school.)

                                  Edited by: jverd on Feb 8, 2011 11:48 AM