Сообщение #6623

[mini_root]

Надеюсь, не грех похвастаться. :-) 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

Ну и? Смотрим условие, используется РЕКУРСИВНОЕ вычисление, а не оптимизированное итеративное (а это оно и есть, ведь так?). Итеративное везде быстро считается, там один цикл и нет ветвящейся рекурсии. Так что смотрим на первое число - 62 секунды.

P.S. Можно поподробнее, что именно делает Memoize? Явно превращает рекурсию в цикл?