Have you ever thought about what would happen if you called a function or method from within that function or method? That’s called recursion and can actually make your program more efficient. It can be used for problems that can be broken up into multiple steps, often ones that you would otherwise solve iteratively. It will also be used in some of the traversal and sort algorithms that you will see later.

Introduction to Recursion

You’ve heard about a trendy new spot that sells fruit sandwiches. What are fruit sandwiches? You have no idea, but you’re eager to find out!

Sadly, when you arrive at the store, the line is out the door and around the block. Undeterred, you hatch a plan to find out how many people are in line before you.

You tap the person in front of you and ask them how many people are ahead of them. They have no idea, (the line is huge!) so they ask you to wait a moment and tap the person in front of them, repeating this process through the line.

Finally, the second to last person taps the person at the front of the line. Nobody is ahead of them, so they reply “It’s just me so: one person!”. Then this message is repeated back down the line.

The next person says “okay, there was one person ahead of me, I’ll add myself… I can tell the person behind me: 2 people in line.”

Each person waiting for a reply:

1. receives the message
2. adds themselves to the count
3. responds to the person tapping them

This chain eventually reaches you with the final number. Your plan was a success!

You executed a recursive strategy. The “function” of asking a person involved asking a person. The self-referential logic can seem like it goes on forever, but each question brings you closer to the front of the line where no more people are asked about the line.

Your approach had two aspects which are essential to recursive thinking. Break the problem into two possibilities:

1. There’s nobody left in line, don’t ask
2. There’s someone in line, ask them

We repeat Step 2 with a different input which brings us closer to Step 1.

_{Image credits to CARP.ca}

Recursion Outline

Recursion is a strategy for solving problems by defining the problem in terms of itself. For example, to sum the elements of a list we would take the first element and add it to the sum of the remaining elements.

How would we get that sum of remaining elements? Easy! We’d take the first element of the remaining elements and add it to the… Maybe you can understand why recursion can be a tricky subject!

In programming, recursion means a function definition will include an invocation of the function within its own body. Here’s a pseudo-code example:

define function, speller
  if there are no more letters
    print "all done"
  print the first letter
  invoke speller with the given name minus the first letter

If we invoked this function with “Zoe” as the argument, we would see “Z”, “o”, and “e” printed out before “all done”.

We call the function a total of 4 times!

1. function called with “Zoe”
2. function called with “oe”
3. function called with “e”
4. function called with “”

Let’s break the function into three chunks:

if there are no more letters
    print "all done"

This section is the base case. We are NOT invoking the function under this condition. The equivalent base case from the previous exercise was when we had reached the front of the line.

print the first letter

This section solves a piece of the problem. If we want to spell someone’s name, we’ll have to spell at least one letter.

invoke speller with the given name minus the first letter

This section is the recursive step, calling the function with arguments which bring us closer to the base case. In this example, we’re reducing the length of the name by a single letter. Eventually, there will be a function call with no letters given as the argument.

For comparison’s sake, here is pseudo-code for an iterative approach to the same problem:

define function, speller
for each letter in the name argument
    print the letter
print "all done"

`

Call Stacks and Execution Frames

A recursive approach requires the function invoking itself with different arguments. How does the computer keep track of the various arguments and different function invocations if it’s the same function definition?

Repeatedly invoking functions may be familiar when it occurs sequentially, but it can be jarring to see this invocation occur within a function definition.

Languages make this possible with call stacks and execution contexts.

Stacks, a data structure, follow a strict protocol for the order data enters and exits the structure: the last thing to enter is the first thing to leave.

Your programming language often manages the call stack, which exists outside of any specific function. This call stack tracks the ordering of the different function invocations, so the last function to enter the call stack is the first function to exit the call stack

we can think of execution contexts as the specific values we plug into a function call.

`
A function which adds two numbers:

Invoking the function with 3 and 4 as arguments...
execution context:
X = 3
Y = 4

Invoking the function with 6 and 2 as arguments...
execution context:
X = 6
Y = 2
`

Consider a pseudo-code function which sums the integers in an array:


function, sum_list
if list has a single element
return that single element
otherwise...
add first element to value of sum_list called with every element minus the first


This function will be invoked as many times as there are elements within the list! Let’s step through:

`
CALL STACK EMPTY

Our first function call...
sum_list([5, 6, 7])

CALL STACK CONTAINS

sum_list([5, 6, 7])
with the execution context of a list being [5, 6, 7]

Base case, a list of one element not met.
We invoke sum_list with the list of [6, 7]...

CALL STACK CONTAINS

sum_list([6, 7])
with the execution context of a list being [6, 7]

sum_list([5, 6, 7])
with the execution context of a list being [5, 6, 7]

Base case, a list of one element not met.
We invoke sum_list with the list of [7]...

CALL STACK CONTAINS

sum_list([7])
with the execution context of a list being [7]

sum_list([6, 7])
with the execution context of a list being [6, 7]

sum_list([5, 6, 7])
with the execution context of a list being [5, 6, 7]

We've reached our base case! List is one element.
We return that one element.
This return value does two things:

1) "pops" sum_list([7]) from CALL STACK.
2) provides a return value for sum_list([6, 7])

CALL STACK CONTAINS

sum_list([6, 7])
with the execution context of a list being [6, 7]
RETURN VALUE = 7

sum_list([5, 6, 7])
with the execution context of a list being [5, 6, 7]

sum_list([6, 7]) waits for the return value of sum_list([7]), which it just received.

sum_list([6, 7]) has resolved and "popped" from the call stack...

CALL STACK contains

sum_list([5, 6, 7])
with the execution context of a list being [5, 6, 7]
RETURN VALUE = 6 + 7

sum_list([5, 6, 7]) waits for the return value of sum_list([6, 7]), which it just received.
sum_list([5, 6, 7]) has resolved and "popped" from the call stack.

CALL STACK is empty

RETURN VALUE = (5 + 6 + 7) = 18
`

Base Case and Recursive Step

Recursion has two fundamental aspects: the base case and the recursive step.

When using iteration, we rely on a counting variable and a boolean condition. For example, when iterating through the values in a list, we would increment the counting variable until it exceeded the length of the dataset.

Recursive functions have a similar concept, which we call the base case. The base case dictates whether the function will recurse, or call itself. Without a base case, it’s the iterative equivalent to writing an infinite loop.

Because we’re using a call stack to track the function calls, your computer will throw an error due to a stack overflow if the base case is not sufficient.

The other fundamental aspect of a recursive function is the recursive step. This portion of the function is the step that moves us closer to the base case.

In an iterative function, this is handled by a loop construct that decrements or increments the counting variable which moves the counter closer to a boolean condition, terminating the loop.

In a recursive function, the “counting variable” equivalent is the argument to the recursive call. If we’re counting down to 0, for example, our base case would be the function call that receives 0 as an argument. We might design a recursive step that takes the argument passed in, decrements it by one, and calls the function again with the decremented argument. In this way, we would be moving towards 0 as our base case.

Analyzing the Big O runtime of a recursive function is very similar to analyzing an iterative function. Substitute iterations of a loop with recursive calls.

For example, if we loop through once for each element printing the value, we have a O(N) or linear runtime. Similarly, if we have a single recursive call for each element in the original function call, we have a O(N) or linear runtime.