In
my previous post, I talked about some of the basics of recursion and why you might want to use it to your advantage. Today, let's dive a little deeper into the different kinds of recursion, including linear, tail recursion and finally binary recursion. This is in a series of back to basics covering recursion in some depth.
Starting Off
Where we left off is to take a simple imperative statement and make it not only recursive, but we could also hypothetically turn it into tail recursive as well. Let's start off with the simple, yet overused factorial example in a very imperative way using looping:
C#
public static int Factorial(int n)
{
var fact = 1;
var i = n;
while (i > 0)
{
fact = fact * i;
i--;
}
return fact;
}
F#
let factorial_imperative n =
let mutable fact = 1
let mutable i = n
while i > 0 do
fact <- fact * i
i <- i - 1
fact
So, what we're left with is mutation galore. That's perfectly ok in the imperative world, but it doesn't make sense to me in the functional world since we have such things as recursion. Functional languages make you go out of your way to make values mutable, because by default they aren't mutable at all.
Linear Recursion
Linear recursion is by far the most common form of recursion. In this style of recursion, the function calls itself repeatedly until it hits the termination condition. After hitting the termination condition, it simply returns the result to the caller through a process called unwinding. Most of my samples I posted in the previous post followed this way of recursion.
C#
public static int Factorial(int n)
{
if (n <= 1)
return 1;
else
return n * Factorial(n - 1);
}
F#
let rec factorial_linear n =
if n <= 1 then 1 else n * factorial_linear (n - 1)
As you noticed, the last call here is a calculation, which helps unwind itself to the termination condition of 1. Of course it's also guarded against negative input as well which would cause an infinite loop, which would be pretty bad. But with large input, this could be a problem.
Tail Calls
As I've mentioned before, it's pretty important to think about the stack when you do recursion. For the reasons of stack overflows, it's pretty important to mention. When you call an F# function, stack space is allocated and then freed when the function returns, or, when a
tail call is performed. We have to be aware of this, because a very deep set of nested function calls will cause a StackOverFlowException to be thrown. Below is a simple example on how this can occur.
#light
let rec recursiveFunc i : unit =
if i >= 1000000 then
()
else
if i % 1000 = 0 then
printfn "Recursing at %i" i
recursiveFunc (i + 1)
printfn "Just called the function with %i" i
recursiveFunc 100
The above function actually recurses, but that's not the last thing the function does. It in turn calls a printf end line function to display the result. If you let this run, you'll get a nice StackOverFlowException and it will take down your F# Interactive (fsi) session. How do you fix this situation? Well, it's a topic called tail recursion which will expand upon this.
Tail Recursion
Tail recursion is a specialized form of the linear recursion where the last operation of the function happens to be a recursive call. The difference here is that in my previous samples, I've been calling functions which perform a calculation on the result of the recursive call. That could lead to stack overflows should the recursion get too deep. Instead, I don't want to do any work during the unwinding phase, just return the value from the function.
Let's take the above sample and make it tail recursive:
#light
let rec recursiveFunc i : unit =
if i >= 1000000 then
()
else
if i % 1000 = 0 then
printfn "Recursing at %i" i
recursiveFunc (i + 1)
recursiveFunc 100
All I had to do was get rid of the last statement and now the last statement is simply a calling of the function again with no work performed. If I run it through the F# interactive again, I get no problems at all, and it runs through smoothly. Let's refactor our factorial to be tail recursive in F#, and then look at a C# solution.
F#
let rec factorial_tail n =
let rec factorial_inner acc x =
if x <= 0I then acc
else factorial_inner (x * acc) (x - 1I)
factorial_inner 1I n
As you can see, the last calls to my recursive inner function is indeed tail recursive as no work is being done to the result of any calls. From there, my outer function should be able to call passing in the accumulator of 1 and the number we're passing in. Since I'm using BigInt, I don't have a problem with overflow either in regards to really large input. This is something that the .NET BCL was working on, but kept it internal in the System.Core.dll it seems. But, F# was nice enough to give us BigNum and BigInt implementations, as F# tends to be rather math centric.
The Problem with C# and Tail Calls
Now turning our attention to the C# counterpart to this, let's try our implementation of the above functionality in it. Instead of just another function, I'll inline the accumulator function inside as an anonymous function:
C#
public static ulong Factorial(ulong n)
{
Func<ulong, ulong, ulong> factorial_acc = null;
factorial_acc = (acc, x) =>
{
if (x <= 0) return acc;
return factorial_acc(x * acc, x - 1UL);
};
return factorial_acc(1UL, n);
}
But the problem is, is that this won't work on a 32 bit machine. Why you might ask? Well, as
Jomo Fisher, an F# team member, points out in his post about
recursion in three languages, the C# compiler does not do tail call optimization. Instead, all managed languages have a second opportunity to optimize through either NGEN or the JIT compiler. As it turns out, the x64 version of the JIT will optimize the tail call right now, whereas the 32 bit compiler will not. By default on your C# projects, it's targeted at AnyCPU which in my case since I'm running on a VPC, targets x86, will cause the overflow, whereas if I had been running on my base machine, it would have been ok.
This is another in the line of reasons why F# is the better language for recursion as well as functional programming fundamentals. C# will get you partially there, but there are things such as these which will trip up developers and leaving themselves nowhere to go. To which I say, pick the best language for the job at hand, whether it be F#, C#, Ruby, Python, Erlang, Haskell, JavaScript, etc.
Binary Recursion
Another form of recursion is binary recursion. This form of recursion has the potential for calling itself twice instead of once as with before. This is pretty useful in such scenarios as binary trees as well as the trite and overused Fibonacci sequence. Such an example is below:
let rec fibonacci n =
if n <= 2 then 1
else fibonacci (n - 1) + fibonacci (n - 2)
But what's interesting is that we could do this better through tail recursion through the use of our inner auxiliary function, such as this:
let fib n =
let rec fib_acc a b x =
if x <= 1 then b
else fib_acc b (a + b) (x - 1)
fib_acc 0 1 n
But, back to the point, here's another use of binary recursion to print out the values in a tree.
type Tree<'a> = | Leaf of 'a | Node of Tree<'a> * Tree<'a>
let rec printBinaryTreeValues t =
match t with
| Leaf x -> printfn "%A" x
| Node (l, r) ->
printBinaryTreeValues l // called once
printBinaryTreeValues r // called twice
printBinaryTreeValues (Node ((Node (Leaf "jeden", Leaf "dwa")), (Node (Leaf "trzy", Leaf "cztery"))))
As you can see from this example, I printed out the values from the binary tree, leaf by leaf using binary recursion.
Wrapping It Up
As you can see here, I've covered a bit of ground on more recursive algorithms. There is still yet more to be covered including processing of lists, unbalanced trees, continuations and so on. More on that soon! In the mean time, I hope you rediscover recursion and what it can do for you in terms of condensing code. But, it's also important to see where it makes sense and where it doesn't.