Kotlin Program to Find Fibonacci Using Recursion

You can write a Kotlin recursive function like fun fibonacci(n: Int): Int = if (n <= 1) n else fibonacci(n - 1) + fibonacci(n - 2) to calculate Fibonacci numbers.

Examples

Input0

Output0

Input5

Output5

Input10

Output55

How to Think About It

To find the Fibonacci number at position n, check if n is 0 or 1, then return n itself because these are the base cases. Otherwise, calculate the sum of the Fibonacci numbers at positions n-1 and n-2 by calling the function recursively.

Algorithm

1

Get the input number n.

2

If n is 0 or 1, return n as the Fibonacci number.

3

Otherwise, call the function recursively for n-1 and n-2.

4

Add the results of the two recursive calls.

5

Return the sum as the Fibonacci number for n.

Code

kotlin

fun fibonacci(n: Int): Int {
    return if (n <= 1) n else fibonacci(n - 1) + fibonacci(n - 2)
}

fun main() {
    val n = 10
    println("Fibonacci number at position $n is ${fibonacci(n)}")
}

Output

Fibonacci number at position 10 is 55

Dry Run

Let's trace fibonacci(5) through the code

1

Call fibonacci(5)

Since 5 > 1, calculate fibonacci(4) + fibonacci(3)

2

Call fibonacci(4)

Since 4 > 1, calculate fibonacci(3) + fibonacci(2)

3

Call fibonacci(3)

Since 3 > 1, calculate fibonacci(2) + fibonacci(1)

4

Call fibonacci(2)

Since 2 > 1, calculate fibonacci(1) + fibonacci(0)

5

Call fibonacci(1)

Return 1 (base case)

6

Call fibonacci(0)

Return 0 (base case)

7

Calculate fibonacci(2)

1 + 0 = 1

8

Calculate fibonacci(3)

fibonacci(2) + fibonacci(1) = 1 + 1 = 2

9

Calculate fibonacci(4)

fibonacci(3) + fibonacci(2) = 2 + 1 = 3

10

Calculate fibonacci(5)

fibonacci(4) + fibonacci(3) = 3 + 2 = 5

Call	Returned Value
fibonacci(1)	1
fibonacci(0)	0
fibonacci(2)	1
fibonacci(1)	1
fibonacci(3)	2
fibonacci(2)	1
fibonacci(4)	3
fibonacci(3)	2
fibonacci(5)	5

Why This Works

Step 1: Base Case

The function returns n directly when n is 0 or 1, stopping further recursion.

Step 2: Recursive Calls

For other values, the function calls itself twice with n-1 and n-2 to build the Fibonacci sequence.

Step 3: Combining Results

The results of the two recursive calls are added to get the Fibonacci number at position n.

Alternative Approaches

Iterative approach

kotlin

fun fibonacciIterative(n: Int): Int {
    if (n <= 1) return n
    var a = 0
    var b = 1
    var c = 0
    for (i in 2..n) {
        c = a + b
        a = b
        b = c
    }
    return c
}

fun main() {
    val n = 10
    println("Fibonacci number at position $n is ${fibonacciIterative(n)}")
}

This method is faster and uses less memory than recursion because it avoids repeated calls.

Memoization (caching results)

kotlin

fun fibonacciMemo(n: Int, memo: MutableMap<Int, Int> = mutableMapOf()): Int {
    if (n <= 1) return n
    if (memo.containsKey(n)) return memo[n]!!
    val result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo)
    memo[n] = result
    return result
}

fun main() {
    val n = 10
    println("Fibonacci number at position $n is ${fibonacciMemo(n)}")
}

This method improves recursion by storing results to avoid repeated calculations.

Complexity: O(2^n) time, O(n) space

Time Complexity

The recursive function calls itself twice for each non-base case, leading to exponential time because many calls repeat the same calculations.

Space Complexity

The maximum depth of the recursion stack is n, so space complexity is linear.

Which Approach is Fastest?

Iterative and memoized methods run in linear time O(n), much faster than plain recursion.

Approach	Time	Space	Best For
Recursive	O(2^n)	O(n)	Small inputs, simple code
Iterative	O(n)	O(1)	Large inputs, performance
Memoization	O(n)	O(n)	Large inputs, recursion style