Сообщение #6619

[marvin]

Надеюсь, не грех похвастаться. :-) Nemerle. Во второй функции используется макрос Memoize, реализующий соответствующую оптимизацию.

Код:

using Nemerle;
using System;
using System.Diagnostics;

namespace Fibonacci
{
  module Main
  {
    static Fib1(n : int) : int
    {
      | 0 => 0
      | 1 => 1
      | _ => Fib1(n - 1) + Fib1(n - 2)
    }
    
    [Memoize]
    static Fib2(n : int) : int
    {
      | 0 => 0
      | 1 => 1
      | _ => Fib2(n - 1) + Fib2(n - 2)
    }
    
    static TestFib(fib : int -> int) : void
    {
      def sw = Stopwatch();
      sw.Start();
      
      def result = fib(46);
      
      sw.Stop();
      
      Console.WriteLine($"Result: $result Time: $(sw.Elapsed.TotalSeconds)");
    }
    
    public static Main() : void
    {
      TestFib(Fib1);
      TestFib(Fib2);
    }
  }
}

Вывод:
Result: 1836311903 Time: 62,7802466
Result: 1836311903 Time: 0,0022332