Recursion - How to overflow the stack and how not to

Recursive functions are functions that calls itself. If you were new to recursive function, it may have hurt your brain. Today's blog is in the similar lines. It may help you understand recursion better.
Fun exercise: Try searching 'recursion' on Google.

We will create a recursive function to find the factorial of a number. A factorial of a number is the product of all the integers before it down until 1. The factorial of 1 is 1. And that is the base case.

let rec fact x =
 if x <= 1 then 1
 else
  x * fact (x-1)

Any recursive function written by humans must have base case or a terminating case. Recursive functions have a tendency to get sucked into a black hole which in turn is a recursive sucker. Luckily when we write recursive functions on computers, the call-stack comes to rescue us from the black hole.

What is the call stack?

A call stack is where function calls are stored. When a function is called, the control needs to go into the function. When the function completes executing, the control needs to go back to the function it was called from. The call stack keeps track of the current executing function and the function it needs to go back to when it finishes executing. The data structure the call stack uses for this is, you guessed it, the stack.

In the title of this blog, I use the word stack. For the purposes of this blog I use stack and call stack interchangeably. A call stack is made up of stack frames. Every stack frame represents a function call. The top-most stack frame represents the latest.

Call stack of the running factorial function.

_{Courtesy: Visual Studio 2017}

The number of frames the stack can hold is finite. When the stack can take no more frames, it is said to be overflowed. That's when you get the infamous stack overflow exception. It is important to learn to break things in order to prevent it from breaking.

Let's get the stack overflow exception deliberately.
Call the above function with a very large number. Say a hundred thousand.

let factorial = fact 100000

And that is how you overflow the stack.

Tail Recursion
Tail recursion is a recursion of a function where it does not consumes stack space and hence prevents stack overflow. If the recursive function is made tail-recursive then it is more efficient than a non-tail-recursive function because every function call does not need to go on stack and pop when the call is done. And it prevents the ugly stack overflow.

Let's create a recursive function to find the sum of integers from 1 to a given n. That will be a parameter to the function. The base case where the recursion stops is when n is zero. Here is the function

let rec sumOfIntegers n =
 if n = 0 then 0
 else
  n + sumOfIntegers (n-1)

If you debug this function, you will notice that every function call consumes a stack space. This function is not tail-recursive. If you notice in the recursive function above, there is a base case and a recursive case. Recursive case is where all the recursion action takes place. The last expression of the recursive case is an addition. When the recursive call is made, it still has to come back after a series of calls to do the addition. If we make the last expression just a recursive call, then we give a chance to the compiler to optimize the recursion so as to not consume stack space. So we can make the above function tail-recursive if we can make the last expression of the recursive case to be just a recursive function call without any other additional evaluation. Here is the tail-recursive version of the sumOfIntegers

let sumOfIntegersTr n =
 let rec sumrec n sum =
  if n<= 0 then sum
  else
   sumrec (n-1) (n+sum)
 sumrec n 0

The function sumOfIntegersTr takes n as an argument. Notice that it is not a recursive function. It defines a nested function sumrec which is recursive. Right after the definition of sumrec, it invokes sumrec.

The recursive function sumrec, looks to be tail recursive because the last expression in its recursive case is just a function call.
sumrec takes 2 argument. n, the obvious one and sum, which it uses to accumulate the sum of number. The first invocation of sumrec is done by the outer function sumOfIntegersTr. It is invoked with n and 0, 0 is the initial value for sum.This way it does the addition in the argument to the function call. The base case returns the accumulated sum. Pretty neat. Debug and take a look at the call-stack to verify.

Now, lets make that factorial function tail-recursive. Remember that the last expression of the recursive case must be just a function call. I will also be using an accumulator named factorial to hold the value of the factorial. Just like sum in sumrec.

let factTr n =
 let rec factRec n factorial =
  if n <= 1I then factorial
  else
   factRec (n-1I) (n*factorial)
 factRec n 1I

Notice the 'I' suffixed to the the integer? It just means that the number is a Big Integer. Its a type to hold large integers. Go ahead and take a look at the call stack, it should consume only one stack frame for any number of calls.

Hope you enjoyed reading this. Until next time. Cheers.