/*****************************************************************************
 * File: fibonacci.decaf
 * Author: Keith Schwarz (htiek@cs.stanford.edu)
 *
 * A sample Decaf program that computes Fibonacci numbers in two ways.
 */

/* Recursive version of the Fibonacci numbers. */
int FibonacciRec(int n) {
    if (n <= 1) return n;

    /* Decaf supports recursion. */
    return FibonacciRec(n - 1) + FibonacciRec(n - 2);
}

/* Iterative version of Fibonacci. */
int FibonacciIterative(int n) {
    /* Variables must be declared at the top of a block and do not support
     * initialization on declaration.
     */
    int a;
    int b;

    a = 0;
    b = 1;

    while (n > 0) {
          /* New variables can be declared at the top of a block. */
          int c;

          /* Compute the next values in the sequence. */
          c = a + b;
          a = b;
          b = c;

          /* Decaf does not support -- or ++, nor does it support compound
           * assignment (-=, +=, etc.)
           */
          n = n - 1;
    }

    return a;
}

int main() {
    Print("The tenth Fibonacci number is ");
    Print(FibonacciRec(10));
    Print("\n");

    Print("The twentieth Fibonacci number is ");
    Print(FibonacciIterative(20));
    Print("\n");
}