DEV Community

Cover image for A Simple introduction to recursion
Anwar
Anwar

Posted on

A Simple introduction to recursion

Recursion is one of the topics that confuses people when seeing it for the first time, this article introduces the main idea of recursion in order to make things a little bit clearer and get you up and running with it.

What exactly is recursion ?

It's easier to understand it through an example

Say you were asked to calculate the sum of 13 and 18, most of us thinks about it like this:

  • since 10 + 10 = 20
  • and 3 + 8 = 11
  • so the sum is 20 + 11 = 31

what exactly did we do here ?

instead of calculating the sum right away, we broke
the problem into two small problems of the same type, the difference is that we can easily solve the two small problems.

That's exactly what recursion is all about, it's about breaking a problem into several small problems that are easier to solve.

Enough talking, let's write some code

Now that you (hopefully) understand the main idea behind recursion, let's see how can we implement it.

Let's start by writing a function that counts from a given number n up to 5 in our console, this is done very easily using a loop like this:

function countTo5(n){ 
    for(let i =n; i<=5; i++){ 
        console.log(i)
    }
}

countTo5(1)
Enter fullscreen mode Exit fullscreen mode

but let's try doing it with recursion (Make sure you read the comment in the code below in order to understand how it works)

function countTo5(n){ 
   if(n === 5) { 
       console.log(n)
       return;
   }
   console.log(n);

   return countTo5(n+1)
}

countTo5(1)
/* 
    first call
    n = 1 
    1===5 ? no 
    console.log(1)
    return countTo5(2)
    -----------------
    second call 
    n = 2
    2===5 ? no 
    console.log(2)
    return countTo5(3)
    -----------------
    third call 
    n = 3
    3===5 ? no 
    console.log(3)
    return countTo5(4)
    ------------------
    forth call 
    n = 4
    4===5 ? no 
    console.log(4)
    return countTo5(5)
    ------------------
    fifth call 
    n = 5
    5===5 ? yes
    console.log(5)
    the function stops
*/
Enter fullscreen mode Exit fullscreen mode

note: it's absolutely better to solve it with loops, recursion is used here for explanation purposes only

Base Case

A loop becomes infinite if we don't have a stopping condition. similar to loops, if recursion doesn't have something that makes it stop it will execute over and over until it causes a stack overflow.

in the example above, our base case was this if statement
if(n === 5) {
console.log(n)
return;
}

In most cases the base case is going to be a conditional statement.

conclusion

  1. recursion is a way of solving problems by breaking it into smaller problems

  2. we can say that recursion is an elegant way of looping

  3. we must have a base case in our recursion or else we'll get stack overflow

Hope this helps guys, this is my first article ever so I'd love to know your opinions about it, hopefully it becomes first of many useful article, here is some further reading and videos

-https://javascript.info/recursion#two-ways-of-thinking

-https://www.youtube.com/watch?v=lMBVwYrmFZQ

-https://www.youtube.com/watch?v=k7-N8R0-KY4

-https://www.freecodecamp.org/news/understanding-recursion-in-javascript/

Top comments (13)

Collapse
 
dakujem profile image
Andrej Rypo • Edited

Chapter one: Tail Recursion.

To understand tail recursion, you need to understand Chapter One: Tail Recursion.

Collapse
 
anwarr_________ profile image
Anwar

This link goes to this article not an article about tail recursion

Collapse
 
dakujem profile image
Andrej Rypo

Come on, man, it's a joke! I updated the link...

Thread Thread
 
anwarr_________ profile image
Anwar

I'm pretty slow at getting jokes, I have just got it now, great one broπŸ˜‚πŸ˜‚πŸ˜‚

Thread Thread
 
anwarr_________ profile image
Anwar

liked the article ?

Thread Thread
 
dakujem profile image
Andrej Rypo

Well, if you're asking... It's curious you did not use the ever-present factorial example. The example provided does not really demonstrate the advantage of recursion. I'd use an example that would otherwise require a stack data structure, like an algo to detect palindromes, for example.

abcba --> true
abcde --> false
Enter fullscreen mode Exit fullscreen mode
Thread Thread
 
anwarr_________ profile image
Anwar

Yeah that's because the goal of writing this article was to clarify the main idea of recursion for absolute beginners, I wanted to make it as simple as possible so I came up with this simple example, maybe in an upcoming article I'll dive more deep into recursion
Thanks for your opinion

Collapse
 
hamzamateen profile image
HamzaMateen • Edited

I think people should first learn how stacks work as function call always endup being on the call stacks. This way we can more rigorously define Recursion in terms of implementation.

Nice article tho!! ❀️❀️

Collapse
 
anwarr_________ profile image
Anwar

Yeah you're right, generally you understand your code better when you learn more about how it works and what happens behind the scenes

Thank a lot bro ❀️️

Collapse
 
almasweb1 profile image
Almas Rakhmatullaev

Good article! I didn't really understand what recursion is yesterday, but after this article I began to understand well. Thank you.

Collapse
 
anwarr_________ profile image
Anwar

Thank a lot man glad I could help

Collapse
 
anwarr_________ profile image
Anwar

your so welcome, thank you for this great feedback :)