module Simple =
// [snippet:Recursive Fibonacci]
/// Inefficient recursive implementation of Fibonacci numbers.
///
/// The problem is that 'fibs 3' will call 'fibs 1' recursively
/// three times. To solve this, we'd like to keep the result of
/// previously calculated function calls using dynamic programming.
let rec fibs n =
if n < 1 then 1 else
(fibs (n - 1)) + (fibs (n - 2))
// [/snippet]
module Memoized =
// [snippet:Reusable memoization function]
open System.Collections.Generic
/// The function creates a function that calls the argument 'f'
/// only once and stores the result in a mutable dictionary (cache)
/// Repeated calls to the resulting function return cached values.
let memoize f =
// Create (mutable) cache that is used for storing results of
// for function arguments that were already calculated.
let cache = new Dictionary<_, _>()
(fun x ->
// The returned function first performs a cache lookup
let succ, v = cache.TryGetValue(x)
if succ then v else
// If value was not found, calculate & cache it
let v = f(x)
cache.Add(x, v)
v)
// [/snippet]
// [snippet:Memoized Fibonacci]
/// Recursive function that implements Fibonacci using memoization.
/// Recursive calls are made to the memoized function, so previously
/// calculated values are retrieved from the cache.
let rec fibs = memoize (fun n ->
if n < 1 then 1 else
(fibs (n - 1)) + (fibs (n - 2)))
// Note - add #nowarn "40" to disable warning complaining about recursive
// value reference. This is not an issue in this snippet.
// [/snippet]