0

I do understand that one of the problems with recursion is the stack depth that can lead to problems in very deep recurrences. Also I am aware that recursion can be replaced by explicit stack usage to avoid such issues.
On the other side, recursion allows for succinct and clear (and beautiful, I would say) code and is the main way to present algorithms in all standard textbooks if I recall correctly.

My question is more practical than theoretical:

I am running the following program to figure out how far can I go before I get a java.lang.StackOverflowError
My reasoning was that e.g. if I had a small graph view a few thousands vertices and minimal processing per traversal, then recursive vs iterative approach might not matter that much:

public static void foo(int i) {
   if (i % 5000 == 0) {
        System.out.println(i);
   }
   foo(i + 1);
}

public static void main(String[] args) {
    foo(0);
}

The output was:

Exception in thread "main" java.lang.StackOverflowError
5000
10000

So from that my interpretation is that the program would blow up after processing just above over 10000 vertices doing a DFS which sounds small.
Googling I found that the default size of the stack can be configurable when we run a program but I wanted to know what is the industry practice on this?

Is it to set explicit thread stack size for heavy server programs so the example above wouldn't be an issue in practice? Or is it to avoid writing recursion altogether? Or is my example not really representative of a problem?

Update
I do understand that the code sample above is an infinite recursion. The only purpose of that was to see how far it would go before it breaks.

fredt
  • 24,044
  • 3
  • 40
  • 61
Jim
  • 3,845
  • 3
  • 22
  • 47
  • The code you've posted is an infinite recursion. There's no config that will make it work. – khelwood Jul 15 '20 at 13:40
  • @khelwood: Yes I do understand that. The only point was to see how far it would go before it breaks down. Nothing else – Jim Jul 15 '20 at 13:41
  • 4
    There's no industry practice that I know of, but it is best to avoid recursive calls when you don't have a language that supports tail-call elimination. Unless, that is, you know the recursion to be very shallow. – Federico klez Culloca Jul 15 '20 at 13:41
  • @FedericoklezCulloca: Do you mean tail recursion? – Jim Jul 15 '20 at 13:42
  • @Jim no, I mean, tail-call elimination, which means that the compiler will, when possible, unroll your recursive calls to avoid a growing stack and basically transform the whole thing into an iteration. Look no further than scheme for a language that does that. – Federico klez Culloca Jul 15 '20 at 13:45
  • If you have tail call recursion, you can hope for [tail call optimisation (TCO)](https://stackoverflow.com/questions/310974/what-is-tail-call-optimization) at the language level. As far as I'm aware, Java doesn't support TCO (yet?). However, all tail call recursion can be kept and "manually" converted to a loop by using [trampolines](https://stackoverflow.com/questions/32685660/achieving-stackless-recursion-in-java-8) - it's a functional technique that requires you to produce thunks (`Runnable` functional interface in Java) instead of an explicit tail call and converts those to a loop. – VLAZ Jul 15 '20 at 13:46
  • So for graph processing, it is the explicit stack usage the common thing for real-life problems? – Jim Jul 15 '20 at 13:48
  • 1
    Code is clean and succinct because it's clear and succinct, not because it's "written recursively". And it also doesn't make it *good code*. For instance, implementing the Fibonacci function (_the_ textbook poster child of recursion) as a recursive function is about the worst implementation in real life, and that goes for many other textbook examples that don't concern themselves with whether what they present is good code in the sense that it's efficient. Recursion has its place as long as the recursion itself is guaranteed shallow enough, and the overhead of the recursion is insignificant. – Mike 'Pomax' Kamermans Jul 15 '20 at 13:50
  • @JohnKugelman tens of thousands is right out! Once you reach the hundreds, being the hundredth numbers, be reached lobbest thou thy recursion :P – VLAZ Jul 15 '20 at 13:51
  • Note that for graph processing, it'd be unlikely that you're not using an appropriate graph datastructure, where you don't have recursion because your code path moves from node to node. (Sure, "node1.whatever()" will call "node2.whatever()", but that's not recursion). You might use a recursive function to do things like collapsing the graph to (sub)paths, but it would certainly get messy because instead of making each node responsible for locally tracking their involvement, you'd have to do _all_ the administration inside that single function. And that would certainly not be beautiful. – Mike 'Pomax' Kamermans Jul 15 '20 at 13:54
  • @Mike'Pomax'Kamermans: Just to clarify. My only thought about characterising the code as "beatiful" was because the code that requires explicit stack management is hidden by the programmer and hence focus more on the problem at task. I didnt mean to make a code style comparison per se. I am sorry if I confused all at the post – Jim Jul 15 '20 at 14:23
  • Question for those who closed the post: Why is it opinion based? Everyone here agrees that recursion must be dealt with caution. So I was looking for a way of how to evaluate it. Is this something that is still a matter of opinion? In other words, can I improve the post somehow? – Jim Jul 15 '20 at 14:30
  • @FedericoklezCulloca ^ – Jim Jul 15 '20 at 14:30
  • @Mike'Pomax'Kamermans ^ – Jim Jul 15 '20 at 14:30
  • 1
    @Jim you're right. I'll vote to reopen. – Federico klez Culloca Jul 15 '20 at 14:33
  • The problem is that those ways are _still opinions_: there is no hard and fast rule for when to use which, other than to literally look at the specific code, in your specific use case, _write out both solutions_ and see which of those is more appropriate to your personal circumstances. Are you optimizing for speed? you probably don't want recursion. Unless this one function is not a bottleneck. Unless unless the requirement is reusable code in other projects. Unless unless unless they're short lived projects. Unless unless unless unless etc. etc. There is not "answer" here, just anecdotes. – Mike 'Pomax' Kamermans Jul 15 '20 at 15:04
  • @Mike'Pomax'Kamermans: `write out both solutions and see which of those is more appropriate to your personal circumstances` this is not what I got from the answers though. What I get here is that with a proper complexity analysis of the algorithm we can come up with the proper approach without actually needing to write out both approaches and benchmark etc. – Jim Jul 15 '20 at 20:38

2 Answers2

3

Is it to set explicit thread stack size for heavy server programs so the example above wouldn't be an issue in practice?

No.

  1. The example is infinite recursion. It will always be an issue.
  2. There is no stack size that would be large enough in Java. It requires an infinite amount of stack space.
  3. (In languages / implementations that implement "tail call optimization", you don't get a stack overflow. But Java is not such a language.)

Or is it to avoid writing recursion altogether?

No. Recursion is fine ... provided you can predict the maximum depth of recursion.

Or is my example not really representative of a problem?

It is not really representative.

However there are clearly real-world problems where a recursive approach will fail for some inputs.

Googling I found that the default size of the stack can be configurable when we run a program but I wanted to know what is the industry practice on this?

There is no relevant "industry practice" for setting the default stack size. The stack size that is required depends on the actual algorithm and its implementation, and the input data.

However, it is a bad idea to try to implement a recursive solution when you cannot place a reasonable bound on the depth of recursion.

It is technically possible to compute the required stack space for a given depth of recursion for a given Java program, but the computation will be platform dependent.

The JVM places limits on the maximum stack size. For example for Java 11 on x86-64 in 64 bit mode, you cannot set -Xss greater than 1g. (Which is probably a good thing.)

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • 2
    `when you cannot place a reasonable bound on the depth of recursion.` This helps. Now I can see the value of making good complexity assessments. This helps, thanks – Jim Jul 15 '20 at 14:24
1

Rough rule of thumb, I get uncomfortable with recursion once the number of calls is in the hundreds. Thousands is definitely too high.

Recursion works great for problems with O(log n) call depth such as binary tree traversal because logarithms scale up so slowly. I'd stay away from using it for O(n) graph algorithms.

John Kugelman
  • 349,597
  • 67
  • 533
  • 578