6

I am trying to prevent a function/method (in Java) from performing recursion more than a depth of 3 self calls. I've learnt about the accumulator trick from odersky's scala coursera course. 

public void myMethod(File arg, int accumulator) {
    //...snipped...
    File newArg= ...;
    if (accumulator + 1 > 3)
        throw new IllegalStateException("exceeeding depth 3");
    myMethod(newArg, accumulator+1);
}

Any other ideas ? Perhaps with a ThreadLocal ?

FrustratedWithFormsDesigner
  • 46,105
  • 7
  • 126
  • 176
socgen hacker
  • 181
  • 1
  • 2
  • 7
  • 3
    What kind of "trick"? Rename "accumulator" to "depth", and you see there is no trick - it is just straightforward counting. And the alternative is just to use a member variable `depth` of the class where `myMethod` belongs to, increase the variable when you enter `myMethod`, and decrease it when you leave the method. – Doc Brown Nov 26 '14 at 22:03
  • Yes it is not a trick. Wrong choice of word to describe it. – socgen hacker Nov 26 '14 at 22:10
  • 1
    Related: [What methods are there to avoid a stack overflow in a recursive algorithm?](http://programmers.stackexchange.com/q/194646/40980) –  Nov 26 '14 at 22:11
  • 2
    What kind of "other way" do you expect? When the obvious, straightforward solution is so simple as in this case, any different solution will most probably be unnecessary complicated. – Doc Brown Nov 26 '14 at 22:25
  • 4
    Is there an underlying issue you're trying to solve? – svidgen Nov 27 '14 at 01:24

2 Answers2

7

Yes, there is another way of limiting recursion depth, but I would not encourage it.

In general, we can say that you are currently using a data-driven approach.

public void myMethod(File arg, int accumulator) {

where the accumulator counts the recursion call depth.

The other way is to enumerate the calls. Said another way, hard-code the calls:

private void myMethodSnippedCode(/*args*/) {
    //...snipped...
}

public void myMethod(File arg) {
    myMethodSnippedCode(/*whatever*/);
    // File newArg= ...; // ... code is moved to the myMethod1 call below
    // Exception removed. Why would you throw an exception?
    myMethod1(...); // the ... is where your new File is created
}

private void myMethod1(File arg) {
    myMethodSnippedCode(/*whatever*/);
    myMethod2(...);
}

private void myMethod2(File arg) {
    myMethodSnippedCode(/*whatever*/);
    myMethod3(...);
}

private void myMethod3(File arg) {
    myMethodSnippedCode(/*whatever*/);
    // don't make any more calls
}

What a code comprehension and maintenance nightmare. If we have to change the number of levels required, or introduce other changes, someone will inevitably get it wrong.

Stick with nice clean recursion that everyone will understand:

public void myMethod(File arg, int depth) {
    // [snipped code body]
    if (depth< 3)
        myMethod(..., ++depth); // the ... is where your new File is created
}

BTW, the initial call to myMethod requires the caller to pass zero. What will happen if they pass 6? Or -21? The solution to this is to wrap the first call

public void myMethod(File arg) {
        myMethodWorker(arg, 0);
}

private void myMethodWorker(File arg, int depth) {
    // [snipped code body]
    if (depth < 3)
        myMethodWorker(..., ++depth); // the ... is where your new File is created
}
andy256
  • 3,156
  • 2
  • 15
  • 20
  • 1
    +1, thanks for elaborating exactly what I wrote in my comment above - different solutions have a high risk of becoming unnecessarily complicated. – Doc Brown Nov 27 '14 at 07:24
1

there are various ways:

  1. rewrite the recursion into an iterative version and you don't have to worry about recursion depth only the stack depth if the iterative version requires one.

  2. Use an outside variable of some kind (static variable, field member,...) to track the recursion depth. This has the downside that it takes up some bytes just for this method and may not be thread-safe/reentrant depending on what type you choose.

However the accumulator method is usually preferable when the iterative version would end up unreadable.

ratchet freak
  • 25,706
  • 2
  • 62
  • 97