Ciwnco

Esto es, para resolver un problema de forma recursiva debes:
1. Confiar en la recursión para resolver una versión más simple del problema
2. Obtener la solución al problema completo a partir de la solución de la versión más simple
La frase confía en la recursión quiere decir que cuando estés analizando el funcionamiento de un programa recursivo y veas una llamada recursiva debes confiaren que esta llamada va a devolver el resultado que se prentende.
Vamos a utilizar estas reglas para construir algunos procedimientos recursivos.
elemento?
Por ejemplo, vamos a empezar analizando desde el punto de vista de las reglas anteriores el siguiente procedimiento, que comprueba si un carácter está en una cadena:
(define (elemento? x palabra)
(cond((empty? palabra) #f)
((equal? x (first palabra)) #t)
(else (elemento? x (bf palabra)))))
El funcionamiento del procedimiento consiste en:
1. Quitamos el primer carácter de la cadena.
2. Si el carácter es la "a" devolvemos true.
3. Sino llamamos a la recursión con el resto de la cadena (un problema más sencillo, porquees una cadena más corta), confiamos en que la llamada recursiva funcione correctamente y devolvemos su resultado.
¿Cuándo para el algoritmo? Cuando el problema es "lo más simple posible" y ya no se puede simplificar más: este es el caso base. Debemos entonces devolver un valor concreto, la recursión ya ha terminado. En el caso del ejemplo se llega al caso base cuando la cadena es vacía, entoncesdevolvemos false.
veces
Otro ejemplo. Veamos el problema de contar el número de veces que un carácter (por ejemplo la "a") aparece en una cadena:
1. Quitamos el primer carácter de la cadena.
2. Llamamos a la recursión con el resto de la cadena (un problema más sencillo, porque es una cadena más corta). Esta llamada nos dice que en el resto de la cadena hay n letras "a".
3. Si elprimer carácter que hemos quitado es una "a" devolvemos n+1, sino devolvemos n.
4. Caso base: cadena vacía. En ese caso devolvemos 0.
La solución en Scheme:
(define (veces c pal)
(if (empty? pal)
0
(if (equal? (first pal) c)
(1+ (veces c (bf pal)))
(veces c (bfpal)))))
pigl
Otro problema: Pig Latin. Pig Latin es una modificación del inglés que usan los niños para hablar de forma divertida. Se trata de modificar una cadena moviendo todas las consonantes (hasta la primera vocal) de su comienzo a su final y añadiendo el sufijo "ay". Por ejemplo, en castellano:
* chaval -> avalchay
* curso -> ursocay
* problema -> oblemapray
Aquí lasolución recursiva es algo más complicada. La primera idea sería hacerlo como los ejemplos anteriores:
1. Si la palabra a modificar empieza por consonante: quitar la consonante, aplicar Pig Latin al resto de cadena.
2. Confiamos en que la recursión nos devuelva el resto de cadena traducida a Pig Latin y entonces añadimos la consonante al final.
3. Caso base: si la cadena empieza porvocal devolver la cadena con el sufijo "ay" añadido.
¿Funciona bien esta solución?
Veamos un ejemplo. Apliquemos Pig Latin a la palabra "problema". Nos debería devolver "oblemapray". Sin embargo, el algoritmo anterior haría lo siguiente:
1. La palabra "problema" comienza por consonante. La quitamos y aplicamos Pig Latin a "roblema".
2. Confiamos en la recursión y devuelve la palabramatraducida: "oblemaray". Movemos la "p" al final: "oblemarayp". NO ES CORRECTO.
¿Cómo habría que plantear la recursión? Si nos fijamos en el ejemplo, nos daremos cuenta de que la "p" debería estar antes del sufijo "ay". Esto se consigue llamando a la recursión después de haber movido la consonante al final de la cadena:
1. La palabra "problema" empieza por consonante, la quitamos y la colocamos al...