Functional Fundamentals: Recursion
I’m learning functional programming, so this article is one in a series of functional oriented blog posts. Click links to read the others:
A for loop is one of the things I use most when dealing with lists of items.
In a pure functional language, like Haskell, there is no for loop. The language forces you to use another means to solve your problems.
F# is not a pure functional language, so it contains a for loop, but if you’re writing idiomatic F# you’re probably not using for loops very much.
Recursion is one way to solve the same problem without using a for loop. Today I wanted to show you what recursion is and how it can be used to solve problems!
What is Recursion
Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.
Most often this presents itself with recursive functions, which are functions that call themselves.
In this F# function, notice one line 3 that factorial calls itself. That’s why it’s recursive, in F# you have to mark a recursive function with the rec keyword.
For Loop v Recursion
Lets take a closer look at factorial. The factorial of a number is the product of that number and all integers below it.
So factorial(4) = 4 * 3 * 2 * 1
And factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
You get the idea.
If I were to do this in C#, my implementation would probably look something like this.
I start at 1, multiplying by each integer until I reach the number passed into the method. Simple enough.
Taking a look again at the F# solution.
You’ll notice that I don’t keep a variable to hold the product. Recursion leverages the fact that the solution problem can be expressed in terms of a smaller instance of that same problem. Then uses the call stack’s natural ability to store state of a local function as it makes another call.
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 * factorial(0)
factorial(0) = 1 //hard coded on line 2
factorial(1) = 1 * 1
factorial(2) = 2 * 1 * 1
factorial(3) = 3 * 2 * 1 * 1
factorial(4) = 4 * 3 * 2 * 1
factorial(4) = 24
Usually a recursive method will recursively call itself until it hits the base case, then as it “unwinds” the stack, it calculates or populates the necessary data.
Leveraging Recursion
When solving a problem recursively, you need to define:
- A base case – our base case was whenever the number equaled 0.
- A reduction step which converges to the base case. 1
- Each nested call of factorial subtracts one from
num, so it gets closer and 0, which is our base case.
- Each nested call of factorial subtracts one from
- Then some logic to determine what to return.
- Factorial just multiples and returns, you’ll see maxElement contains more logic around return value.
Lets say we wanted to define a function to find the max value of an int list. Lets define a base case and reduction step for that function.
Base case – when our list is empty
Reduction step – calling the recursive function with a progressively smaller list.
Logic to determine return – find out what is the max element.
It would probably look something like this:
I’m still learning F#, some there’s probably some room for improvement.
Notice how our base case is defined on line 2, if the list is empty return None to represent no max. In C#, I’d probably choose null or Int.MinValue here, but the F# Option type gives us better choices.
Reduction step is on line 4, calling maxElement with the tail of the list.
Head and Tail are functional terms for identifying the first and the rest of the elements of a list. If a list = [1, 2, 3, 4] then Head = 1, Tail = [2, 3, 4], also if a list = [a, b, c, d] then Head = a, Tail = [b, c, d]
Our logic is contained on lines 5-8 to determine determine which is the maxElement at this point in our list. Returning either the current element, or the max of the tail of the list.
Tail Recursion
While recursion is neat and can make solving certain problems very intuitive, it does come with some performance issues.
Recursion makes heavy use to the stack. Every call to the recursive method, the runtime has to save local variables, call the function, then when it returns pop everything off the stack again. Depending on what problem you’re solving, that can add up.
Tail Recursion is particular sort of recursive method where the recursive call is the last operation in the method.
If that’s the case, compilers that support Tail Recursion Optimization can easily convert your method to a loop like approach to prevent stack overflows and give you better performance.
My maxElement method above does not use Tail Recursion, because there are operations (lines 5-8) that occur after the recursive call.
My factorial method also does not use Tail Recursion. The recursive call is on the last line in method, but the multiplication is actually the last operation to complete.
If I wanted to change my factorial to use Tail Recursion I would introduce what’s called an accumulator. An accumulator it used to store the intermediate calculations of my function, therefore eliminating the need for the stack to do that.
Notice how factorialLoop takes a parameter called acc (short for accumulator), and on line 6 the multiplication occurs before calling the recursive function, instead of afterwards in my original method. That’s the key difference between the two methods.
F# is a language that supports Tail Recursion Optimization, so if you’re dealing with a lot of recursion of performance critical code, keep this in mind.
Final Thoughts
Functional languages force a different thought process in order to solve problems. Recursion is one example of how you can achieve the same outcome as a for loop. While most imperative languages also support recursion, it’s use is normally not emphasized.
I’m looking forward to learning more about functional concepts, I hope you choose to too!
References: