Recursion in F#
When talking about recursion the example that everyone thinks of is the fibonacci numbers, get a book on algorithms and you can almost bet your house that that algorithm is there.
First off, just like C# and all other languages if you don't have a case(s) that your recursive case gets ever closer to in the recursive case then you are going to eventually just smash the stack to bits resulting in some overflow exception - F# just like C# and any other managed language will eventually throw a StackOverflowException.
Here is a bad fibonacci algorithm (you'll probably never see this anywhere - it's that bad!). This algorithm only has a recursive case, the fib function is going to call itself forever resulting in a StackOverflowException.
let rec fib n =
match n with
| n -> fib (n - 1) + fib (n - 2)
I'm not quite sure if the above example is at all relevant, the point I'm trying to make is that all functional languages use recursion immensely when processing any form of data so it's important to remember the basics of recursion:
- Base case(s) (usually the very easy bits that you can do quite quickly)
- Recursive case (the harder bit, this should ultimately call your base case(s))
With that in mind here is the correct fibonacci algorithm.
let rec fib n =
match n with
| 1 -> 1
| 2 -> 1
| n -> fib (n - 1) + fib (n - 2)
This example isn't exclusive to F#, you can go ahead and replicate this in C# or C/C++ very easily. Here is the C++ example (and yes, I know I'm assuming the input is positive - this should work for C# also).
int Fib(int n) {
if (n < 3) return 1;
return Fib(n-1) + Fib(n-2);
}
The recursive implementation of fibonacci is very expensive, pass in a fairly large number and you witness the expense of recursion in this case, draw out a recursive tree for the number 9 and you will see something that's pretty big - and 9 is pretty small.
There is a case where by 0 returns 0, I've omitted that. The maths function definition for fibonacci is here.