Recursion For Beginners

#recursion #javascript

One topic that stumped me as a beginner programmer was the concept of recursion. It’s something that seems to never be used outside of programming, and it’s advantages aren’t quite obvious, making it something not-too-easy to understand. This is an attempt to effectively explain recursion to anyone who isn’t sure what it is, how it works, or why it’s useful.

What is Recursion?
According to Webster Dictionary, recursion is:

“a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first”

But what does that even mean? We already know it’s a computer programming technique, but under what conditions would you want a function to call itself?

Basically, recursion is the concept of having a function call itself until it has done whatever it needs to. This is kind of like a loop (and some languages actually use recursion AS their loops under the hood), but the key difference is that loops (iteration) work by explicitly specifying a repetition structure, whereas recursion achieves repetition by continuous method calls. Consider the following task:

Create a method that takes any two numbers as parameters and runs the fibonacci sequence algorithm on them 100 times, and displays the output for each step.

Iteratively, you may do so like this:

const fib = (a, b) => {   // Create the method
  counter = 0              // Instantiate a counter
  while(counter < 100) {     // Loop until the counter reaches 99 
    sum = a + b
    console.log(sum)
    a = b                  // Reassign the variables for the next iteration
    b = sum
    counter++
  }
}

fib(4,5);                   // Call the function

This gives you the desired results, and works fine. Recursively, though, it would look something like:

fib = (a, b, counter = 0) => { // Create the method
  if (counter > 100) return // Check exit condition
  counter++
  console.log(a + b)
  return fib(b, a + b, counter) // Call itself again if exit condition isnt met
}

fib(4,5)

As you can see, they both give the same results, but the recursion is slightly shorter and easier to read. Recursion allows for management of exponential growth. While recursion is useful in many cases, there are also cases when it is better to solve the problem iteratively. Recursion is usually more memory intensive, so it may not be the best option for solving problems that require minimal memory usage.

Top comments (3)

Kushan Joshi • Aug 2 '18 • Edited

Javascript has started supporting Tail Call optimisation. This means that we no longer have to worry about memory consumption or stack overflow when choosing recursion over iteration, of course you have to make sure you write your recursion in a way which can be Tail Call optimised.