Created
May 31, 2012 08:44
-
-
Save paradoja/2841976 to your computer and use it in GitHub Desktop.
Recursividad final
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment