• Post Reply Bookmark Topic Watch Topic
  • New Topic

Inquisitive question on the difference between two main methods for recursion  RSS feed

 
David Vach
Ranch Hand
Posts: 105
3
Chrome Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi all, so I have been messing around with recursion and I found two different ways of getting my result from the main method. However, I'm not sure which is better to use or if both are just fine to use. Just some simple curiosity about the differences in using each or if there are any really at all. Thanks everyone! Heres the two different samples of code:



My other main method which uses the same recursive and iterative methods:



Just an inquisitive question.
 
Fred Kleinschmidt
Bartender
Posts: 571
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In your iterativeMethod(), there is no need to start with i=0, since adding zero to zero has no effect.
Another way to do it would be

Note that this is fine for integers, but if the addition is for a large number of real numbers, or for numbers that have very large variations, it is better to start by adding the smallest values first. Can you see why?

For a large number of values, the iterative method may prove better, since you could encounter a StackOverflow for the recursive method.
 
David Vach
Ranch Hand
Posts: 105
3
Chrome Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah I definitely can. It also makes sense why you wouldn't want the compiler to go through adding 0 when it has no over all effect on the output. However, I still have two questions. Is there any difference between the two main methods that I made for this program and why would the recursive method encounter a StackOverflow over the iterative method?
 
Fred Kleinschmidt
Bartender
Posts: 571
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If your initial argument is 10000, you will end up with 10000 copies of the method on the stack.
 
David Vach
Ranch Hand
Posts: 105
3
Chrome Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ohhhhh that makes sense. Thanks.
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Fred Kleinschmidt wrote:If your initial argument is 10000, you will end up with 10000 copies of the method on the stack.

Technically, this is not correct. Each method call creates what's called a stack frame, not a copy of the method per se. A stack frame is a block of information that includes information to manage program execution as well as the parameters passed to the method and local variables needed by the method. See this article for more details: http://www.fredosaurus.com/JavaBasics/methods/methods-25-calls.html

Other JVM-based languages like Scala and Kotlin support what's called tail call optimization which basically turns a tail-recursive call into an iteration under the covers. The code is still written as a recursive call but the compiler will optimize the executable code so that stack use is very efficient and there's no danger of getting a stack overflow. A tail call version of the function we're discussing here would look something like this:

Unfortunately, Java does not support tail call optimization so this code can still blow the stack for sufficiently large values of n.

You can still achieve tail call recursion in Java though. Here's an article that explains how: https://medium.com/@johnmcclean/trampolining-a-practical-guide-for-awesome-java-developers-4b657d9c3076#.txyiy8z1e

Tail recursion and Trampoline functions are not a beginner level topic though.
 
Damon McNeill
Ranch Hand
Posts: 67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
All the possibilities of implementing real tail-call optimization in Java have problems. By "proper", I mean no additional space, at all, is required to perform the call in tail position. Techniques like trampolining simply consumes heap space instead of stack space... that's not an optimization. Sure, it avoids the stack overflow, but it eats up the heap. Tail call optimization should not eat up stack or heap.
 
Campbell Ritchie
Marshal
Posts: 56546
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please explain more about those techniques; this is the “beginning” forum and many people here are unfamiliar with those terms.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!