Kotlin Tail-Recursive function: Calculate the nth Fibonacci

Last update on February 04 2025 10:57:59 (UTC/GMT +8 hours)

Write a Kotlin tail-recursive function to calculate the nth Fibonacci number.

Pre-Knowledge (Before You Start!)

Before solving this exercise, you should be familiar with the following concepts:

• Fibonacci Sequence: The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, typically starting with 0 and 1. The sequence looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, etc.
• Tail Recursion: A function is tail-recursive when the recursive call is the last operation in the function. This helps optimize performance by not creating extra stack frames, allowing the function to handle large inputs efficiently.
• Base Case: In recursion, the base case is the condition that stops the recursion. For Fibonacci, the base case is when n is 0, in which case the function should return 0.
• Recursive Case: The recursive case involves calculating the next Fibonacci number by summing the previous two values and recursively calling the function with updated parameters.

Hints (Try Before Looking at the Solution!)

Here are some hints to help you solve the problem:

• Hint 1: The Fibonacci sequence starts with 0 and 1, so initialize two variables to hold these values.
• Hint 2: For each recursive call, decrement n and calculate the next Fibonacci number by adding the two previous ones.
• Hint 3: Make sure to pass the updated values of the previous Fibonacci numbers to the recursive function.
• Hint 4: Use the tailrec modifier to ensure the function is optimized for large values of n and avoids stack overflow errors.
• Hint 5: The recursion should stop when n reaches 0, returning the value of the current Fibonacci number.

Sample Solution:

Kotlin Code:

tailrec fun fibonacci(n: Int, a: Long = 0, b: Long = 1): Long {
    if (n == 0) {
        return a
    }
    
    return fibonacci(n - 1, b, a + b)
}

fun main() {
    val n = 9
    val fibonacciNumber = fibonacci(n)
    println("The $n-th Fibonacci number is: $fibonacciNumber")
}

Sample Output:

The 9-th Fibonacci number is: 34

Explanation:

In the above exercise -

• The "fibonacci()" function takes three parameters: n, which represents the position of the Fibonacci number to be calculated, a and b which are used to keep track of the previous two Fibonacci numbers.
• In the base case, if n becomes 0, it means we have reached the desired position and return the current Fibonacci number a.
• In each recursive call, we decrement n by 1 and calculate the next Fibonacci number by adding the previous two Fibonacci numbers (a + b). The current value of b becomes the new value of a, and the sum a + b becomes the new value of b.
• We use tail recursion by making the recursive call directly without additional computation.
• The recursive calls continue until the base case is reached and the final Fibonacci number is computed.

Kotlin Editor:

Previous: Sum of numbers from 1 to n.
Next: Calculate the power of a number.