DEV Community

loading...

How to Replace Loops using Recursion

rthefounding profile image Randy Rivera ・2 min read

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
Enter fullscreen mode Exit fullscreen mode
  • 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
}
}
Enter fullscreen mode Exit fullscreen mode
console.log(sum([2, 3, 4, 5], 3)); will display 9
Enter fullscreen mode Exit fullscreen mode
// 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;
Enter fullscreen mode Exit fullscreen mode

Discussion (7)

Collapse
theowlsden profile image
Shaquil Maria

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

Collapse
wireless90 profile image
wireless90

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

Collapse
cariehl profile image
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.

Thread Thread
theowlsden profile image
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.

Collapse
rthefounding profile image
Randy Rivera Author • Edited

You definitely could but for this I used Recursion.

Collapse
cariehl profile image
Cooper Riehl • Edited

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!

Collapse
theowlsden profile image
Shaquil Maria

Great feedback!

Forem Open with the Forem app