Kotlin recursive function: Sum of even Fibonacci numbers

Last update on February 04 2025 08:26:41 (UTC/GMT +8 hours)

From Wikipedia,
In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted Fn . The sequence commonly starts from 0 and 1, although some authors start the sequence from 1 and 1 or sometimes (as did Fibonacci) from 1 and 2. Starting from 0 and 1, the first few values in the sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.

Write a Kotlin recursive function to calculate the sum of the even Fibonacci numbers up to a given limit.

Pre-Knowledge (Before You Start!)

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

• Fibonacci Sequence: A series of numbers in which each number is the sum of the two preceding ones. It starts from 0, 1 and continues with 1, 2, 3, 5, 8, 13, 21, 34, etc.
• Recursion: A function calling itself to solve a problem incrementally.
• Even Numbers: Numbers that are divisible by 2 without a remainder.
• Base Case in Recursion: The point at which the recursive function stops, typically when a certain condition is met (e.g., when the current Fibonacci number exceeds the limit).

Hints (Try Before Looking at the Solution!)

Here are some hints to help you solve the problem:

• Hint 1: Use recursion to generate the Fibonacci numbers, passing the previous and current numbers to the next recursive call.
• Hint 2: Check if the current Fibonacci number is even using the modulo operator (%) and add it to the sum if it is.
• Hint 3: Continue the recursion until the current Fibonacci number exceeds the given limit.
• Hint 4: Ensure the function can track the sum of the even Fibonacci numbers across recursive calls.

Sample Solution:

Kotlin Code:

fun sumEvenFibonacci(limit: Int): Int {
    return sumEvenFibonacciHelper(0, 1, 0, limit)
}

fun sumEvenFibonacciHelper(prev: Int, current: Int, sum: Int, limit: Int): Int {
    if (current > limit) {
        return sum
    }
    
    val newSum = if (current % 2 == 0) sum + current else sum
    
    return sumEvenFibonacciHelper(current, prev + current, newSum, limit)
}

fun main() {
    val limit = 12
    val sum = sumEvenFibonacci(limit)
    println("Sum of even Fibonacci numbers up to $limit: $sum")
}

Sample Output:

Sum of even Fibonacci numbers up to 12: 10

Explanation:

In the above exercise -

The "sumEvenFibonacciHelper()" function takes four parameters: prev and current represent the previous and current Fibonacci numbers, sum represents the sum of the even Fibonacci numbers, and 'limit' specifies the upper limit.

The function follows these steps:

• If the current Fibonacci number exceeds the 'limit', we have reached the end of the sequence. In this case, the function returns the current sum.
• If the current Fibonacci number is even, it adds it to the sum using the newSum variable.
• The function then calls "sumEvenFibonacciHelper()" function with the current Fibonacci number as the new previous. It also uses the sum newSum as the updated sum, and generates the next Fibonacci number by adding the prev and current numbers.
• The recursive call continues until the current Fibonacci number exceeds the limit, and the final sum is returned.

In the "main()" function, we define a limit variable representing the upper limit of the Fibonacci sequence. We call the sumEvenFibonacci function with this limit and store the result in the sum variable. Finally, we print the sum to the console

Kotlin Editor:

Previous: Sum of digits in a string.
Next: Find maximum depth of binary tree.