This discussion is archived
13 Replies Latest reply: Feb 8, 2011 11:48 AM by 796440 RSS

mutual recursion without threading

801092 Newbie
Currently Being Moderated
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 Guru
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Guru
    Currently Being Moderated
    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 Guru
    Currently Being Moderated
    Assuming he wants co-routining, that isn't it.
  • 5. Re: mutual recursion without threading
    gimbal2 Guru
    Currently Being Moderated
    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 Expert
    Currently Being Moderated
    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 Guru
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Guru
    Currently Being Moderated
    Did you try Google? I found this top of the list.
  • 10. Re: mutual recursion without threading
    796440 Guru
    Currently Being Moderated
    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 Guru
    Currently Being Moderated
    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 Expert
    Currently Being Moderated
    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 Guru
    Currently Being Moderated
    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

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points