eph baum dot dev

← Back to blog

Iteration v. Recursion

Published on 06/24/2023 01:13 PM by Eph Baum

Featured Image

I was chatting recently with another engineer who was sharing  their desire to have started working through leetcode problems sooner in their career. They, having recently been let go from their gig, like so many folks I know, are working toward leveling up while on the hunt for their next job.

During our conversation I was asked:

Would you say that anything that is iterative is essentially recursive?

My response was:

Not exactly but this feels like a blog post… 😅
While you could say that every problem you can solve iteratively can technically be solved using recursion, there are important distinctions between the two

So now I’m writing a blog post about this topic, I guess 😂

What is Iteration?

Iteration, in the context of programming, is the repetition of a process within a computer program to generate an outcome. This can be accomplished using various control structures, such as ‘for’, ‘while’, and ‘do-while’ loops.

For instance, consider the problem of adding all the numbers in an array. An iterative solution might start with a variable set to zero, loop through each element in the array, and add that element’s value to the variable. The loop repeats until it has processed every element in the array.

The advantage of iterative solutions is their efficiency, especially in terms of memory. Because they update the current state directly and don’t have to keep track of multiple layers of function calls, iterative solutions often use less memory than their recursive counterparts. The word often is doing some work here, and I’m sure I might catch hell for using it, but I believe it’s apt.

What is Recursion?

Recursion is a method where the solution to a problem depends on smaller instances of the same problem. Essentially, a recursive function calls itself with a different argument until it reaches a base case — a condition where it can return a result without any further recursion.

Let’s return to our array addition problem. A recursive solution might take the first number in the array, add it to the result of a recursive call with the rest of the array, and return that sum. The base case occurs when the array is empty, at which point the function returns zero.

Recursive solutions can be more intuitive and easier to understand for certain problems, especially those involving tree or graph traversals, backtracking, and problems that naturally fit into a divide-and-conquer strategy.

Challenges for Recursion

While recursion can make code shorter and easier to write, it comes with its own set of challenges. Each recursive call adds a layer to the system’s call stack, which uses memory to keep track of return addresses and local variables. If the depth of recursion is too high, it could lead to a stack overflow — a common pitfall when using recursion.

Iteration v. Recursion?

Family Guy's Peter Griffin Points to the Movie Screen where a character has said the name of the film in a film and says "Ah. Ah. He Said It."

While every problem that can be solved iteratively can technically also be solved recursively, and vice versa, the two are not the same. The choice between iteration and recursion often depends on the specific problem, the constraints of the task, and the specific language you’re using.

In general, recursion is suited for problems where the task can naturally be divided into subproblems that are similar to the original. On the other hand, iteration is usually better suited for tasks that involve a straightforward repetition of the same process.

Want Some Examples?

Sure you do. Let’s consider two common programming problems and solve them using both iterative and recursive approaches: calculating the factorial of a number and summing the elements of an array.

1. Factorial of a number

The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It’s denoted by n!.

Iterative Approach:

function factorial_iterative(n) {
    let result = 1;
    for (let i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

Recursive Approach:

function factorial_recursive(n) {
    if (n === 0 || n === 1) {
        return 1;
    } else {
        return n * factorial_recursive(n - 1);
    }
}

2. Summing the elements of an array

This problem involves calculating the total sum of all elements in an array, as mentioned above. These two code snippets should provide a reasonable illustration of the differences in behaviors between these two approaches.

Iterative Approach:

function sum_iterative(array) {
    let result = 0;
    for (let i = 0; i < array.length; i++) {
        result += array[i];
    }
    return result;
}

Recursive Approach:

function sum_recursive(array) {
    if (array.length === 0) {
        return 0;
    } else {
        return array[0] + sum_recursive(array.slice(1));
    }
}

In both examples, you can see that the iterative solutions involve looping through a range or an array and directly updating the result, whereas the recursive solutions involve breaking the problem down into smaller sub-problems, solving them, and combining the results.

While these problems are simple, they provide a clear illustration of the difference between iteration and recursion, and how you can use each technique to solve the same problem in different ways.

You’d Like a Conclusion, Perhaps?

Iteration and recursion are two fundamental techniques that every programmer should understand. Each has its strengths and weaknesses, and knowing when to use one or the other can make your code more efficient, readable, and elegant.

Keep in mind that the choice between recursion and iteration isn’t always an either/or decision. Sometimes, the best solution involves a mix of both. Ultimately, the best strategy is to become comfortable with both iteration and recursion, and to understand how and when to use each one effectively.

For some relevant reading, checkout the Church-Turing Thesis

Written by Eph Baum

← Back to blog
  • 50 Stars - Puzzle Solver (of Little Renown)

    50 Stars - Puzzle Solver (of Little Renown)

    Join Eph Baum as they recount their journey through the Advent of Code 2023. For the first time, Eph completes all puzzles, leveraging resources like GPT-4 and Code Llama. Despite the challenges and time constraints, Eph not only stays on top of the puzzles but also lands on the top 1,000 leaderboard. Dive into this post to explore the role of generative AIs in problem-solving and the joy of coding puzzles. - GitHub Co-pilot

  • Don't Trust AI - An Advent of Code Tale

    Don't Trust AI - An Advent of Code Tale

    Join Eph Baum in 'Don't Trust AI - An Advent of Code Tale' as they navigate the Advent of Code 2023. Despite the December rush, Eph is determined to complete all puzzles. This post shares an intriguing incident where an AI-generated code line proves less than helpful. Eph's journey underscores the importance of verifying AI suggestions, especially when optimizing code. Dive in to explore the challenges and triumphs of coding puzzles, and the role of AI in this process. - GitHub CoPilot

  • Condoning Another Pi Day

    Condoning Another Pi Day

    Placeholder description for imported post from Ghost Blog

  • ANSI Terminal Colors

    ANSI Terminal Colors

    Placeholder description for imported post from Ghost Blog

  • WTF is Idiomatic

    WTF is Idiomatic

    Placeholder description for imported post from Ghost Blog

  • From Early Return in OOP to Control Flow in Elixir - A Transition Guide

    From Early Return in OOP to Control Flow in Elixir - A Transition Guide

    Placeholder description for imported post from Ghost Blog