En la entrada anterior hablé sobre la recursividad mediante Scheme y la función de Ackermann. Hay algo curioso, o al menos a mi me sorprende, sobre Scheme y es como interpreta como iterativos algoritmos aparentemente recursivos. Como ejemplo 2 algoritmos para calcular los números de Fibonacci, uno recursivo y el otro iterativo aunque parezca recursivo. Primero recordar que estos números de definen así:
0 Si n = 0
1 Si n = 1
Fib(n – 1) + Fib(n – 2) Si n ≠ 0 y n ≠ 1
Esta definición lleva directamente a este algoritmo recursivo en Scheme:
(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))
Funciona pero es poco eficiente, la complejidad aumenta exponencialmente a medida que el número que buscamos, n, es mayor, pues se trata de recursividad en árbol. Este otro algoritmo es mucho más eficiente:
(define (fib n) (fib-iter 1 0 n)) (define (fib-iter a b count) (if (= count 0) b (fib-iter (+ a b) a (- count 1))))
Si queremos saber el Fibonacci para 4 lo invocamos así:
(fib 4)
Y hará:
(fib 4)
(fib-iter 1 0 4)
(fib-iter 1 1 3)
(fib-iter 2 1 2)
(fib-iter 3 2 1)
(fib-iter 5 3 0)
3
Scheme lo ejecuta como iterativo, no como recursivo. ¿Pero que sucede si implementamos ese mismo algoritmo en un lenguaje tipo procedimental como C o Pascal? Veamos como podría ser en PHP, el rey de la web:
function fib ($a, $b, $aCalc) { if ($aCalc == 0) { return $b; }else{ $aCalc--; fib($a + $b, $a, $aCalc); } } $result = fib (1, 0, 4); echo $result;
Y no funcionará. ¿Por qué? Pues porque PHP lo interpretará como recursivo, no como iterativo, y hará:
(fib 1 0 4)
(fib 1 0 4)(fib 1 1 3)
(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)
(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)(fib 3 2 1)
(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)(fib 3 2 1)(fib 5 3 0)
Pero en vez de quedarse aquí empezará a hacer los «returns», los «pops» de la pila:
(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)(fib 3 2 0)
(fib 1 0 4)(fib 1 1 3)(fib 2 1 1)
(fib 1 0 4)(fib 1 1 2)
(fib 1 0 3)
:-/
Entonces, ¿como hacer «entender» al compilador o intérprete en este tipo de lenguajes que deseamos una implementación iterativa? La única opción es hacer servir las instrucciones que disponen para bucles: while, for, repeat, etc. Este podría ser un ejemplo en PHP:
function fibonacci($n) { $f[0] = 0; $f[1] = 1; for ($i = 2; $i <= $n; $i++) { $f[$i] = $f[$i-1] + $f[$i-2]; } echo $f[$n]; } fibonacci(8);
Ésta curiosidad se puede expresar también a la inversa: Scheme interpreta como iterativos algoritmos que a quienes estamos acostumbrados a los lenguajes por preocedimientos (procedural languages) nos parecen iterativos. Probablemente ésta es mejor forma de expresarlo.
Muy buena explicación
Gracias Miguel, me alegra saber de personas a quienes les resultan interesantes mis artículos.