La recursión idiota
Esta semana me he peleado con un comportamiento extraño de mi intérprete de scheme: las recursiones funcionaban a veces sí, a veces no.
Finalmente y gracias a los compañeros de comp.lang.scheme se ha resuelto el misterio.
(define (factorial n) (if (= n 0) 1 (* n (factorial (- 1 n)))))
En esta recursión tan básica, que calcula el factorial de un número hay un error grave que mete al intérprete en una torre de llamadas recursivas no resueltas (hasta agotar la pila). Salta a la vista (cuando te lo dicen) que (- 1 n) es distinto a (- n 1).
Cuando mi llamada recurente era del tipo (- 1 n) la expresión (factorial 2) generaba
(factorial 2) (* 2 (factorial (- 1 2)) (* 2 (factorial (-1)) (* 2 (* -1 (factorial (- 1 -1)))) (* 2 (* -1 (factorial (2)))) en definitiva: (* 2 (* -1 (* 2 (* -1 (* 2 ....
Así que el código correcto es
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))