Recursividad final

factorial.java

/* Este factorial es recursivo, pero operamos de alguna forma la
 * llamada recursiva (la multiplicamos por n).
 */

long factorial(long n) {
    if (n == 0) {
	return 1;
    }
    else {
	return n * factorial(n-1);
    }
}

/* Este factorial no es recursivo, pero la función auxiliar
 * factorial_helper sí. Aquí, la llamada recursiva no se toca, sino
 * que se devuelve entera. *Eso* es recursividad final (tail call).
 */

long factorial_helper(long n, long ac) { 
    if (n == 0 ) { 
	return ac; 
    } 
    else { 
	return factorial_helper(n -1, n * ac); 
    }
}

long factorial(long n) {
    return factorial_helper(n, 1);
}

fibo.java

/* Este fibonacci es recursivo, pero no recursivo final, pues hacemos
 * algo con las llamadas tras hacerlas (sumarlas entre sí). 
 */

long fibo(long n) {
    if (n == 0 || n == 1) {
	return 1;
    }
    else {
	return fibo(n-1) + fibo(n-2);
    }
}

/* Aquí, como antes, fibo_helper, sí es recursivo final. Haz una traza
 * para ver cómo furula.
 */

long fibo_helper(long n, long last, long prev) {
    if (n == 0) {
	return last;
    }
    else {
	return fibo_helper(n-1, last+prev, last);
    }
}

long fibo(long n) {
    return fibo_helper(n, 1, 0);
}