Using Recursion

Recursion in Computer Science is a method for solving problems. More specifically in programming, you can create recursive functions to solve problems.

Above you can see Google’s definition of recursion with a ‘Did you mean: recursion’ which unlike other ‘Did you mean:’ links usually on Google when you have a spelling error this link just puts you in an endless (recursive) link to the same page.

So, above is the definition for recursion. But to define recursion in programming and for functions, there are two cases we need to think about the recursive case and the base case.

The recursive case is the case in the function where we are calling the function again. When we call the function again in the recursive case we usually need to change something while calling it again like the parameters being passed into the function. So that each time the function is called it is working its way towards a solution and not just a repetitive loop.

Our function being called with different parameters alone is not enough to get us out of an infinite repeative loop. This is where the base case is required in order to break us out of a loop and have our function come to a resolution. The base case is usually defined by an if statement, that when a certain condition is met it will break out of recursively calling itself and return a result.

Overall, in most cases, I’ve seen recursion used the function can also simply be written iteratively and it’s not even the most efficient solution for or more efficient than the iterative case. It does, however, shorten code and if you understand recursion a recursive function is easy to understand.

One of the first problems I used recursion for was the Fibonacci sequence (it’s not an efficient solution) below is the recursive function.

function fibonacci(n) {
  if (n < 2) {
    return n
  }
  return fibonacci(n-1) + fibonacci(n-2)
}

So in this example, you can see the recursive case is calling Fibonacci with the parameter n being reduced by 1 and 2 respectively and adding them. The base case for this problem is when n gets below 2 we simply return n. Like most things with coding to get better with recursion you have to practice coding it out and using it yourself to solve problems.

Working through Udemy courses JavaScript Algorithms and Data Structures Masterclass, Master the Coding Interview: Data Structures + Algorithms & practice stepping through problems helped me to understand and use Recursion.