Simple Recursion Practice

The topic of our lesson today is Simple Recursion in Practice. As you may already know, recursion is a fundamental concept in computer science and an essential skill to master for any serious programmer. Using recursion can simplify code and make it easier to understand, although it can sometimes be hard to grasp initially. Basically, it is a method in which the solution to a problem is based on solving smaller instances of the same problem.

Let's quickly examine a factorial calculation, which is a classic example of recursion. In math, the factorial of a number n is the product of all positive integers less than or equal to n. The logic is straightforward: the factorial of n can be calculated by multiplying the number n by the factorial of n - 1.

In a recursive function, the code calls itself with a modified argument until it reaches a base case. For factorial, the base case is 0, where we return 1 (since the factorial of 0 is 1 by definition). Without a base case, the function would call itself indefinitely, eventually leading to a stack overflow error.

Here is how the solution looks in Kotlin:

fun factorial(n: Int): Int {
    // Base case: factorial of 0 is 1
    if (n == 0) {
        return 1
    } else {
        // Recursive case: multiply n by factorial of n-1
        return n * factorial(n - 1)
    }
}

fun main() {
    // Example usage
    println(factorial(5))  // Outputs 120
}

While recursion is powerful, it can sometimes be inefficient. For example, in a standard Fibonacci sequence, a naive recursive approach calculates the same values over and over again. This leads to redundant work and slow performance as n grows.

To solve this, we use Memoization. Memoization is an optimization technique where we store the results of expensive function calls in a cache (like a MutableMap) and return the cached result when the same inputs occur again.

Here is the general pattern:

1. Check if the result for the current input is already in the map.
2. If it is, return it immediately.
3. If not, calculate the result using recursion.
4. Store the result in the map before returning it.

By using a MutableMap<Int, Long> to cache results, we can turn an exponential time complexity into a linear O(n) one, making the function much faster.

Understanding both simple recursion and memoization is crucial for mastering algorithms and data structures. This lesson provided the foundation; now it is time to practice these techniques to see how they handle nested calls and state management efficiently!