jueves, 28 de mayo de 2015

Source code: C++ Fibonacci Recursion Test

Código fuente del programa C++ Recursion Test

Ver la entrada correspondiente en el siguiente enlace:


Más sobre Recursividad Terminal (Tail Recursion)


#include <iostream>

using namespace std;

static int g_n;
static double g_one;
static double g_two;
static double g_f;
#define pseudocall_fibonacci_goto_inner() goto l_start

double fibonacci_goto_inner() {
l_start:
    if (g_n <= 0) {
        g_f= 0;
    }
    else if (g_n == 1) {
        g_f= g_one;
    }
    else {
        double tmp= g_one + g_two;
        g_two= g_one;
        g_one= tmp;
        g_n= g_n - 1;

        pseudocall_fibonacci_goto_inner(); //goto l_start;
    }

    return g_f;
}

double fibonacci_goto(int n) {
    g_one= 1;
    g_two= 0;
    g_n= n;
    g_f= -1;

    return fibonacci_goto_inner();
}
//------------------------------------------------------------------------------


double fibonacci_iter(int n) {
    double f;
    
    if (n <= 0) {
        f= 0;
    }
    else if (n == 1) {
        f= 1;
    }
    else {
        double two= 0;
        double one= 1;

        for (int i= 2; i <= n; i++) {
            f= one + two;
            
            two= one;
            one= f;
        }
    }
    
    return f;
}
//------------------------------------------------------------------------------


double fibonacci_rec(int n) {
    double f;
    
    if (n <= 0) {
        f= 0;
    }
    else if (n == 1) {
        f= 1;
    }
    else {
//        f= fibonacci_rec(n - 1) + fibonacci_rec(n - 2);
        double one= fibonacci_rec(n - 1);
        double two= fibonacci_rec(n - 2);
        f= one + two;
    }
    
    return f;
}
//------------------------------------------------------------------------------


double fibonacci_tail_inner(int n, double one, double two) {
    double f;

    if (n <= 0) {
        f= 0;
    }
    else if (n == 1) {
        f= one;
    }
    else {
//        f= fibonacci_tail_inner(n - 1, one + two, one);
        double tmp= one + two;
        two= one;
        one= tmp;
        n= n - 1;

        f= fibonacci_tail_inner(n, one, two);
    }

    return f;
}

double fibonacci_tail(int n) {
    return fibonacci_tail_inner(n, 1, 0);
}
//------------------------------------------------------------------------------


int main() {
    //Don't use MAX > 50 with natural recursion, it becomes extremely slowly.
    int MAX= 10;
    //Disable for big values of MAX.
    bool OUTPUT= true;
    double tmp;

    cout << "Iterativo" << endl;
    for (int i= 0; i < MAX; i++) {
        tmp= fibonacci_iter(i);
        if (OUTPUT == true) {
            cout<< "Fibonacci(" << i << ")= " << tmp << endl;
        }
    }
    cout << "Resultado(" << MAX-1 << ")= " << tmp << endl;
    cout << endl;

    cout << "GOTO" << endl;
    for (int i= 0; i < MAX; i++) {
        tmp= fibonacci_goto(i);
        if (OUTPUT == true) {
            cout<< "Fibonacci(" << i << ")= " << tmp << endl;
        }
    }
    cout << "Resultado(" << MAX-1 << ")= " << tmp << endl;
    cout << endl;
 
    cout << "Recursivo terminal" << endl;
    for (int i= 0; i < MAX; i++) {
        tmp= fibonacci_tail(i);
        if (OUTPUT == true) {
            cout<< "Fibonacci(" << i << ")= " << tmp << endl;
        }
    }
    cout << "Resultado(" << MAX-1 << ")= " << tmp << endl;
    cout << endl;

    cout << "Recursivo" << endl;
    for (int i= 0; i < MAX; i++) {
        tmp= fibonacci_rec(i);
        if (OUTPUT == true) {
            cout<< "Fibonacci(" << i << ")= " << tmp << endl;
        }
    }
    cout << "Resultado(" << MAX-1 << ")= " << tmp << endl;
    cout << endl;

    return 0;
}

No hay comentarios:

Publicar un comentario