I have a function that calculates the Fibonacci series with recursion.

fun fibonacciRecursive(n: Long): Long {
    if (n <= 1) {
        return n
    }

    return fibonacciRecursive(n - 1)   fibonacciRecursive(n - 2)
}

It works, but if the number is big then it takes a long time to execute. I've heard that kotlin has a keyword tailrec which improves the recursion and rewrites the function as a loop. But when I add this keyword to this function, the compiler tells A function is marked as tail-recursive but no tail calls are found. Why I can't add tailrec?

CodePudding user response：

Tail recursion is a type of recursion where at each level no calculation needs to be done after the recursive call - it just calls the deeper lever, and the result at the deepest level is the result of the entire stack of calls.

In essence, you can forget about each intermediate level, and when you get to the "bottom", just take the result and give it immediately to the original caller.

In your case, you have to call the next level, wait for it, then another, wait for it, then sum it - that means you do not have a tail-recursion implementation since you have to do something in the intermediate levels after the recursive calls.

The Fibonacci sequence (as all recursive solutions) can be solved iteratively with a regular loop that does not require a large call stack that will eventually also slow you down. It would be good practice to try that implementation, though by definition this sequence is "hard" to compute and quickly requires many iterations. This can also give you a hint on how to re-write it as a tail recursion:

1. Each iteration n given x_n and x_n-1, You set x_n-1 = x_n, x_n = x_n x_n-1 (or something similar).
2. You do this until the requested amount of iterations, where there immediately you have the final sum.

Here we don't need to "go back" to finish our calculation. So in your implementation of a tail recursion instead of passing only the iteration index, you need to pass x_n and x_n x_n-1, so at the final level you will already have the sum - no need to "go back". Tail recursion is essentially recursion that can easily be transformed to a loop.

CodePudding user response：

If you want to use tail-recursion, you usually need to write your algorithm accordingly. In case of Fibonacci, probably the easiest way to turn it into a tail recursive function is to calculate upwards instead of downwards:

(Unfortunately I have no idea about Kotlin, so code below is in Common Lisp).

(defun fibo-slow (n)
  "The classic, non- tail recursive way..."
  (if (<= n 1)
      n
      (  (fibo-slow (- n 1))
         (fibo-slow (- n 2)))))

(defun up (n i-1 i-2 i)
  "Tail recursive 'kernel', passing the history as arguments."
  (if (= i n)
      (  i-1 i-2)
      (up n (  i-1 i-2) i-1 (  i 1))))

(defun fibo-up (n)
  "The adapter for function up, so the interface remains the same as 'fibo-slow'."
  (case n
    (0 0)
    (1 1)
    (otherwise 
     (up n 0 1 1))))

As you can see, in fibo-slow, the tail position is the addition ( ), not the call to the recursive function(s).