Here is James’s solution to Euler 2
// rec means a recursive function
let rec fib x y n =
// returns n if we've reached the end point
if y>4000000 then n
else if (y%2=0) then fib y (x+y) (n+y)
else fib y (x+y) n
let z= fib 1 2 0
printfn "%i" z
As I’ve avoided (like the plague) recursive functions in the past, I though this would be a great opportunity to start!
“Functional programming relies on recursive functions heavily since imperative looping structures are frowned upon” – from a blog on tail recursion http://blogs.msdn.com/b/chrsmith/archive/2008/08/07/understanding-tail-recursion.aspx
A recursive function is a function which calls itself. eg a factorial function 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720
// Non recursive factorial function - negative
let fact x =
let mutable product = 1
//for i in x.. -1 ..1 do
for i = x downto 1 do
product <- product * i
product
from http://en.wikibooks.org/wiki/F_Sharp_Programming/Recursion
fact(6) =
= 6 * fact(6 - 1)
= 6 * 5 * fact(5 - 1)
= 6 * 5 * 4 * fact(4 - 1)
= 6 * 5 * 4 * 3 * fact(3 - 1)
= 6 * 5 * 4 * 3 * 2 * fact(2 - 1)
= 6 * 5 * 4 * 3 * 2 * 1 * fact(1 - 1)
= 6 * 5 * 4 * 3 * 2 * 1 * 1
= 720
let rec fact x =
if x < 1 then 1
else x * fact (x - 1)
Started at 6, then built up the recursive callstack. Now if I keep debugging it will come up the hierarchy evaluating? as it goes.
// can we see the evaluation as it happens by putting in a mutable? ie half way through coming back up the hierarchy what is the total?
let rec fact x =
if x > 2 then
x * (fact (x - 1))
else
x
I find this easier to read
Tail Recursion
A tail recursive funcion is a special case of recursion in which the last instruction executed in the method is the recursive call… as a result, rail-recursive functions can recursive indefinately without consuming stack space.
Notice the Call Stack only has the most recent call on it – it doesn’t need to remember where it is.
let rec count n =
// 1 million
if n = 1000000 then
printfn "done"
else
if n % 1000 = 0 then
printfn "n: %i" n
count (n + 1) (* recursive call *)
count 0
To make it non tail recursive, put in a () after the count, which would return a unit after every call, thus ensuring that the stack has to be kept.