Recursion

Recursion is a core concept in Computer Science that is rarely used. But, for certain problems, algorithms, and solutions — understanding recursion is extremely important. Now, what is recursion? Let’s find out.

 

What Is Recursion

Let’s get the definition of recursion straight from Wikipedia: Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. This means you’re constantly making the initial problem smaller until you get to the smallest aspect of the problem, otherwise known as the base case. This case is usually the most fundamental problem, so let’s get in-depth on this by showcasing a recursive example of summing an array of numbers.

Here’s a live code run for more clarification:

LiveCodeRunRecursion

Now, let’s break down this recursive code.

 

Code Breakdown

In the example above, we create a recursive sumArray function that takes an array and a length that represents the array’s current length. Within the function, we figure out the most important case, the base case on line 12. The base case would be an array with just a single element (length of 1). The reason this is so important is that without a base case, the function would never end; it would have no point where it makes sense to stop invoking the function logically.  Now after that, we figure out every other case (line 15), which is an array with more than one element. Considering our problem is a summation,  we’d want to add the current index of the array, with the next element of the array (line 19), and so on.

Notice that it’s similar to a loop (iterative) solution, except backwards, starting from largest to smallest.

If you notice on line 19, we call the same function again, this is what makes the function recursive. We call a new function with slightly different parameters; it’s similar to create stairs from the top. We constantly “shorten” the array by saying length – 1. You can see the iterations on line 18; we work from the end to the beginning (5, 6, 7, 8, 9, 10 is the base case) of the array. This is an example of the stairs; in Computer Science it is known as the call stack. When we get to the base case, we return; this return adds the previous element to the other one (10 + 9 + 8 + 7 + 6 + 5), going back up the call stack. This is the core of recursion. The most important elements being the call stack and the base case; understanding what your base case is the key to writing a good recursive function. Furthermore, many recursive functions follow this similar if else pattern, so memorize it. Take the time to figure out your base case in any problem.

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s