Avoid Stack Overflow during Recursive Functions

Hello World!

So I’m sure many of you have written recursive functions.  There are many reasons to use recursive functions, usually because the problem is most easily solved through recursion.  The largest downfall however to standard recursive functions is that they continually add onto the function stack, and given enough iterations through can cause a stack overflow.

As you will see, these examples are written in F#, you can do this in C# as well.  So how do you actually deal with it?  Well lets do a simple recursive summation function to demonstrate.

Regular Recursive Functions

//recursive function
let rec sum x =
    if x < 1
    then x
    else x + (sum (x - 1))

//sum 3 blows out into this
sum 3
3 + sum 2
3 + (2 + sum 1)
1 + (2 + (1 + sum 0))
3 + (2 + (1 + 0))
//results in 6

So very simply, a recursive function is a function which has at minimum two branches.  One branch is a termination branch, which returns a result, in this instance an integer.  The other branch executes this same function within the context of the function.  In the example above, this will not cause an overflow, however in the world of big data, you can run out of stack space.

Enter Tailed Recursion

//tailed recursive function
let tailedSum(value:int) =
    let rec tailedSumm x f =
        if x < 1
        then f()
        else 
            tailedSumm (x-1) (fun () -> x + f())
    tailedSumm value (fun() -> 0)

//tailed recursive function valuation
tailedSum(3)
//Blows out into this
//tailedSumm(3, 0)
//tailedSumm(2, 1)
//tailedSumm(1, 2)
//tailedSumm(0, 3)
//6

So lets look at this a little bit.  Tailed recursion takes a second parameter, which is known as an accumulator (sometimes annotated acc).  This accumulator keeps track of the previous state of the recursive function.  This allows for execution of each successive recursive call as though it is just a new call without adding onto the stack further.

The example above takes advantage of functional languages allowing the accumulator to be a function.  You may wish to do this for more advanced recursive functions.  Note that in our instance this function is simply evaluated to an integer.

I wrap the tailed recursive function in a function that a consumer of my function would expect.  As the next function call is supposed to be an iteration of the previous, you will see the next function call is x-1, while the accumulator is x+f() (or the previous value passed in).  This is the principal.  In a summation, this is easy, just realize that the state of your previous call is what should be passed into the accumulator, which should be called when your termination branch occurs, while your non termination branch should make a “recursive call”, which is stateful.

Summary

I hope you found this useful.  The take away should be, no matter what, use tailed recursion, because you know that you cannot have a stack overflow doing this route.  If you go with regular recursion, you face the possibility of encountering a stack overflow exception.  Enjoy and happy coding!

 

Leave a Reply

Your email address will not be published. Required fields are marked *