The Recursive Solution

This second program uses recursive subgoals to generate the fibonacci number. The intuitive idea when implementing a recursive solution is, for fib(i), to recursively generate fib(i-1) and fib(i-2). This would lead to the following program:

  package examples.fibonnacci;
  
  agent RecFib {
      module System system;
      module Console console;

      rule +!main(list args) {
          long S = system.currentTimeMillis();
          !fib(20l, long X);
          console.println("Duration: " +
              (system.currentTimeMillis() - S));
          system.terminate();
      }

      rule +!fib(long N, long R) : N < 3 {
          R = 1;
      }
  
      rule +!fib(long N, long R) {
          !fib(N-1, long A);
          !fib(N-2, long B);
          R = A + B;
      }
  }

This second program, while it initially looks much nicer, is in fact much slower because of the recursive calls. The execution time on this algorithm is exponential – in working out !fib(N-1), the agent works out !fib(1) – !fib(N-2) and then throws it away before calculating !fib(N-2)!