Win a copy of Head First Android this week in the Android forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Rob Spoor
  • Devaka Cooray
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Jj Roberts
  • Al Hobbs
  • Piet Souris

Recursion

 
Ranch Hand
Posts: 373
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What does this method do? I'm confused because I don't know what the parameter result it.
 
Marshal
Posts: 16631
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
result is an accumulator. It's a mechanism that allows a compiler to perform tail call optimization on your recursive code. Let me rephrase that: An accumulator helps you structure your recursive call so that it is a tail call and can be optimized by a compiler that is capable of doing so such that no new stack frames are created on the call stack.

As far as I know, Java doesn't do tail call optimization, by the way. Scala does though, and so does Kotlin.
 
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
this multiply the result with n factorial..

so, if you have say n = 3, result = 2 in that case it calculates 3! (factorial) and multiply it with 2.
 
Saloon Keeper
Posts: 24532
167
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:
As far as I know, Java doesn't do tail call optimization, by the way. Scala does though, and so does Kotlin.



As far as I know, it does. Tail recursion and loop unrolling are some of the oldest and most common optimizations compilers have done and the Java compiler is pretty aggressive.
 
Sheriff
Posts: 8102
571
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Tim Holloway wrote:

Junilu Lacar wrote:
As far as I know, Java doesn't do tail call optimization, by the way. Scala does though, and so does Kotlin.



As far as I know, it does. Tail recursion and loop unrolling are some of the oldest and most common optimizations compilers have done and the Java compiler is pretty aggressive.


I think Junilu is right on that one. At least remember that from university.

However, researching if anything changed recently, found only one seems to be clearly written blog, which claims that you could achieve similar effect with functional Java constructs.
Blog post I'm referring to is: https://blog.knoldus.com/tail-recursion-in-java-8/
 
Tim Holloway
Saloon Keeper
Posts: 24532
167
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I had to go check on that, since, like I said, tail-call optimization (TCO) is pretty standard. Apparently it wasn't considered desirable on older JVMs because each "call" would require a separate stack frame, and even if the frame held no data, it was assumed important that you know how many "calls" had been made in case an Exception was thrown and you needed an accurate stack trace. But that was considered a problem to be solved, not a final solution itself.

I think, in fact, that Java 8 supports TCO, although I'm not 100% sure. In any event, as long as it doesn't do anything that violates the spec, it's the compiler author's choice, so not only which JVM version you use matters, but also whose.
 
Junilu Lacar
Marshal
Posts: 16631
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It's easy to test: just execute some code that shouldn't blow the stack if TCO were applied, like try to get a very large factorial.

From everything I've found, the Java compiler doesn't support TCO but there are ways you can implement it, apparently: https://blog.knoldus.com/tail-recursion-in-java-8/
 
Junilu Lacar
Marshal
Posts: 16631
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I tried this in JShell:

This is a tail call recursive version of Fibonacci. I can get the stack to blow up if I call fib(29569) but it looks like it's getting numeric overflow long before it even gets that high.

I'm running JDK 13:

Junilus-MacBook-Pro:~ jlacar$ jshell
|  Welcome to JShell -- Version 13.0.1
|  For an introduction type: /help intro
 
Junilu Lacar
Marshal
Posts: 16631
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I got this in the Kotlin REPL:

>>> fun fib(n: Int, a: Long = 1L, b: Long = 0L): Long {
...    return if (n == 0) b else fib(n-1, a+b, a)
... }


>>> fib(1)
res74: kotlin.Long = 1

>>> fib(2)
res75: kotlin.Long = 1

>>> fib(3)
res76: kotlin.Long = 2

>>> fib(4)
res77: kotlin.Long = 3

>>> fib(5)
res78: kotlin.Long = 5

>>> fib(20000)
java.lang.StackOverflowError

>>> tailrec fun fib(n: Int, a: Long = 1L, b: Long = 0L): Long {
...    return if (n == 0) b else fib(n-1, a+b, a)
... }


>>> fib(20000)
res83: kotlin.Long = -4378934567125391099

>>> fib(200)
res84: kotlin.Long = -1123705814761610347

>>> fib(10)
res85: kotlin.Long = 55

>>> fib(100)
res86: kotlin.Long = 3736710778780434371

>>> fib(20)
res87: kotlin.Long = 6765

>>> fib(30)
res88: kotlin.Long = 832040

>>> fib(40)
res89: kotlin.Long = 102334155

So in Kotlin, you need to mark a function with tailrec to make the compiler do TCO.
 
Tim Holloway
Saloon Keeper
Posts: 24532
167
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Bear in mind, however, that JVMs and Java compilers both often have several different optimization levels, both explicit and implicit (debug mode often disables many optimizations). So any determinations need to be made based on actual use conditions.

Also, if a recursive method has local variables, it will need a new stack frame for each call level, and it's the stack frame creation that is often the most expensive part of a method call, not the actual call itself.
 
Bartender
Posts: 2899
150
Google Web Toolkit Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am not sure if java does tail optimisation or not, but I think OP's question might not be answered here.

Ana Smith wrote:What does this method do?


The name of the the method is factorial and it looks like it does exactly that: Calculates the factorial of a number and returns the result.
The factorial of a number "n" is : n x (n-1) x (n-2) x .... x 1
if you analyze this mathematically, the factorial of a whole number n can be defined also as n! = n x (n-1)! where (n-1) > 0
This means that the number is multiplied by the next factorial recursively until it reaches 1. Obviously, if you dont stop at 1, you'll reach 0 and we dont want that.

Ana Smith wrote: I'm confused because I don't know what the parameter result it.


Whoever wrote that method wanted to use it in a recursive way and hence (as Junilu pointed out above), needed to accumulate the value in some result. The first call to the factorial function should pass result as 1 as result since 1 is a multiplicative identity.
Remember to always QuoteYourSources whenever you post a code that's not written by you.
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic