Kotlin recursion vs Java Recursion

Support
1

Hello.
I was solving this problem in LeetCode which you should reverse a string. I used the Kotlin language to solve it and wrote a recursive function:

class Solution {
    fun rec(s: CharArray, i: Int, j: Int) {
        if (i >= j) return
        val t = s[j]
        s[j] = s[i]
        s[i] = t
        rec(s, i + 1, j - 1)
    }

    fun reverseString(s: CharArray): Unit {
        rec(s, 0, s.lastIndex)
    }
}

which works for the small test cases. But it fails to pass one of the test cases which is an array of ~53k elements. Then I looked at solutions and saw a Java solution which is identical to mine

class Solution {
    public void rec(char[] s, int i, int j) {
        if (i >= j) return;
        char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
        rec(s, i + 1, j - 1);
    }

    public void reverseString(char[] s) {
        rec(s, 0, s.length - 1);
    }
}

This does pass all tests and is an acceptable answer to the solution.
Can someone explain why the Java solution passes but the Koltin one doesn’t?

P.S I know that using tailrec does solve the problem. Also, have tried to read the generated bytecode but I am not good at understanding it.

EDIT Forgot to mention that the kotlin solution fails by throwing Stackoverflow exception.

Thanks in advance.

1 Like
2

Why in Kotlin you have thi call:

rec(s, i + 1, j - 1)

but in Java this one instead?

helper(s, i + 1, j - 1);
3

This is not a reasonable way to reverse a string. Stack space is limited in Java and Kotlin, and shouldn’t be wasted.

With a 50K character input, your call stack will get up to 25K calls deep. With the default 1MB stack size, that allows less than 40 bytes for each stack frame. It may fit in Java, but just. The Kotlin environment probably just has a few more methods on the stack when yours is called.

A good rule of thumb is that a practical recursive algorithm should use no more than O(log N) stack space for inputs of size N.

4

oops, that was a error in my side! renamed helper function to rec but forgot to fix the place it got called. sorry. :sweat_smile:

5

I know there are better ways to reverse a string. It just wanted to know why it works in Java and not in Kotlin just out of curiosity :smile: Thanks for explanation.

6

How it fails?

rec is a tailrec function :wink:

7

The Kotlin solutions fails by throwing StackOverflow exception

8

In the if you didn’t replace the i and j

1 Like
9

Java does have automatically tail call optimization(TCO) while Kotlin doesn’t, you’ve to mark your function with tailrec explicitly to enable the optimization.

10

That’s interesting. Can you prove somehow that Java optimizes those calls? When I made a test then I got java.lang.StackOverflowError in both Java & Kotlin unless I used tailrec modifier.

11

That is not true.

According to an article from 2014:

It’s important to note that this isn’t a bug in the JVM. It’s an optimization that can be implemented to help functional programmers who use recursion, which is much more common and normal in those languages. I recently spoke to Brian Goetz at Oracle about this optimization, and he said that it’s on a list of things to be added to the JVM, but it’s just not a high-priority item. For now, it’s best to make this optimization yourself, if you can, by avoiding deeply recursive functions when coding a functional language on the JVM.

Source: Tail Call Optimization and Java | Dr Dobb's

2 Likes
12

I for one would not like an automatic tailrec optimization, because the optimization can be easily broken by even slight changes to the functions implementation. Suddenly the optimization would not be applied anymore at runtime. I like that Kotlin yields a compilation error when the function is declared tailrec without correct implementation.

The keyword serves as a documentation for my co-developers, too. They cannot accidentally break my tail recursion.

4 Likes
13

@aminmsvi Did you find real cause of this problem, if yes, please share.
I’m also facing same issue. Same code in java working fine but in Kotlin throwing Stack Overflow.
See this code in link, java version works but Kotlin doesn’t.

14

I strongly suspect that Kotlin generates some synthetic method to do handle the difference between void and Unit as return type

15

Hello, rec method can be called from Java, so Kotlin has to check whether is CharArray nullable. Because of that, it will drain stack faster than the Java version.

Generated code

public final class Solution {
   public final void rec(@NotNull char[] s, int i, int j) {
      Intrinsics.checkParameterIsNotNull(s, "s");
      if (i < j) {
         char t = s[j];
         s[j] = s[i];
         s[i] = t;
         this.rec(s, i + 1, j - 1);
      }
   }

   public final void reverseString(@NotNull char[] s) {
      Intrinsics.checkParameterIsNotNull(s, "s");
      this.rec(s, 0, ArraysKt.getLastIndex(s));
   }
}

Making rec method private should fix the problem as it won’t have to check nullability of the array.

16

How does the call to Intrinsics.checkParameterIsNotNull impact stack usage?

17

I don’t mean that one, I mean that it may create both public final void rec(...) and public final Unit rec(...) where the unit one calls the void one (so Java code can safely override – I know it is a final method, the compiler is not that smart yet). Normally this indirection is insignificant and can be optimized away, but it does interfere with your stack.

18

Assuming that you are correct and using private can help in such cases, is this also valid for internal?

19

No, it is not, as internal methods can be still called from Java.

1 Like