How to Replace Loops using Recursion

Recursion is the concept that a function can be expressed in terms of itself. To help understand this, start by thinking about the following task: Add the first n elements of an array to create the result of those elements. we can rewrite sum in terms of itself and never need to use a loop.

• Here is a for loop for this example:

function sum(arr, n) {
    var product = 0;
    for (var i = 0; i < n; i++) {
        product += arr[i];
    }
    return product;
  }

console.log(sum([2, 3, 4, 5], 3)); will display 9

• Here we write a recursive function, sum(arr, n), that returns the sum of the first n elements of an array arr.
• Note: Recursive functions must have a base case when they return without calling the function again (in this example, when n <= 0), otherwise they can never finish executing.

function sum(arr, n) {
if (n <= 0) {
  return 0;
} else {
  return sum(arr, n - 1) + arr[n - 1]; //return sum(arr, n - 1) <—-calls itself
}
}

console.log(sum([2, 3, 4, 5], 3)); will display 9

// sum([2, 3, 4, 5], 3 - 1) + arr[3 - 1];
// sum([2, 3, 4 ,5], 2) + arr[2];
// sum([2, 3, 4, 5], 2) + 4;
//        n = 2

// sum([2, 3, 4, 5], 2 - 1) + arr[2 - 1];
// sum([2, 3, 4, 5], 1) + arr[1];
// sum([2, 3, 4, 5], 1) + 3; 
//      n = 1             3

// sum([2, 3, 4, 5], 1 - 1) + arr[1 - 1];
// sum([2  3, 4, 5], 0) + arr[0];
// sum([2, 3, 4, 5], 0) + 2;
//      n = 0             2

//      we hit our base case so now n = 0

// 0 + 2 + 3 + 4 = 9
// we want it to return 9 because 4 + 3 + 2 = 9;

Comments

[Shaquil Maria]

I have a question. Why would you use recursion instead of a for or while loop?

[wireless90]

Its easier to think recursively for harder problems. Like tower of hanoi or solving sudoku.

[Cooper Riehl]

Notably, this varies from person to person. Some people think more effectively in terms of recursion, while others find it easier to use iteration. Neither one is inherently wrong, they just have pros and cons to be aware of.

[Shaquil Maria]

Aight aight, thanks for clarifying it for me. When I was starting with Java, we touched based on recursion and I use it from time to time, but I forgot if originally it had an effect on complexity and execution.

[Randy Rivera]

You definitely could but for this I used Recursion.

[Cooper Riehl]

Good example! This is a very approachable one, because the idea of "adding two numbers together" is fairly universal, and a simple example makes it easier to understand a complex concept.

I have a few small pieces of feedback on this article, which you're welcome to consider, discuss, and/or disagree with :)

1. The title of your post has an implied "Always" at the beginning. That is, some people will interpret the title as "Always Replace Loops Using Recursion", which is often not the case (in some scenarios, loops are a better tool to use than recursion). I think a more accurate title would be "How To Replace Loops Using Recursion", which matches the content better.
2. In your description of the task, you say "Add the first n elements of an array to create the product of those elements." I think you meant to use the term "result" instead of "product" - "product" usually means "the result of multiplication", i.e. the product of 2 and 3 is 2 * 3 = 6.
3. In your first sentence, you say "Recursion is the concept that a function can be expressed in terms of itself." In your example, I would recommend directly pointing out the code that makes sum a recursive function (specifically, the fifth line, where it calls itself). This explicitly shows your readers how the concept appears in code, which can help them reinforce the core idea.

Thanks for the article, feel free to respond!

[Shaquil Maria]

Great feedback!