PDF de programación - Recursividad

Recursividad
 

Recursividad
 
Programación
 2
 

 
Los
 términos
 recurrencia,
 recursión
 o
 recursividad
 hacen
 referencia
 
a
 una
 técnica
 de
 definición
 de
 conceptos
 (o
 de
 diseño
 de
 procesos)
 en
 
la
 que
 el
 concepto
 definido
 (o
 el
 proceso
 diseñado)
 es
 usado
 en
 la
 
propia
 definición
 (o
 diseño).
 

 Un
 ejemplo
 paradigmático
 sería
 el
 del
 triángulo
 
de
 Sierpinski
 en
 el
 que
 cada
 triángulo
 está
 
 
compuesto
 de
 otro
 más
 pequeños,
 compuestos
 s
 
su
 vez
 de
 la
 misma
 estructura
 recursiva
 (de
 
hecho
 en
 este
 caso
 se
 trata
 de
 una
 estructura
 
fractal)
 

 

Otro
 caso
 de
 estructura
 recursiva
 son
 las
 
denominadas
 Matryoshkas
 (o
 muñecas
 
rusas):
 donde
 cada
 muñeca
 esconde
 en
 su
 
interior
 otra
 muñeca,
 que
 esconde
 en
 su
 
interior
 otra
 muñeca
 que
 …,
 hasta
 que
 se
 
llega
 a
 una
 muñeca
 que
 ya
 no
 escode
 nada.
 

 En
 nuestro
 caso
 nos
 preocuparemos
 de
 los
 
métodos
 (funciones
 o
 acciones)
 recursivos:
 aquéllos
 en
 los
 que,
 
dentro
 de
 las
 instrucciones
 que
 los
 forman,
 contienen
 una
 llamada
 a
 sí
 
mismos.
 
Como
 siempre,
 la
 parte
 más
 compleja
 no
 será
 a
 nivel
 de
 programación,
 
sino
 a
 nivel
 de
 diseño:
 dado
 un
 problema,
 ser
 capaz
 de
 encontrar
 una
 
solución
 recursiva
 del
 mismo.
 Por
 tanto,
 deberemos
 ser
 capaces
 de
 
pensar
 recursivamente.
 
Algunos
 de
 los
 problemas
 que
 veremos
 ya
 los
 sabéis
 resolver
 
iterativamente
 y
 es
 bueno
 comparar
 las
 soluciones
 recursivas
 que
 
veremos
 con
 las
 iterativas
 que
 
 podéis
 realizar
 por
 vuestra
 cuenta.
 

J.M.
 Gimeno
 y
 J.L.
 González
 


 

1
 


 

Recursividad
 
Programación
 2
 

 
Antes
 de
 empezar
 con
 las
 llamadas
 recursivas,
 recordaremos
 
brevemente
 cómo
 funcionan
 las
 llamadas
 entre
 funciones
 y
 cómo
 éstas
 
modifican
 el
 flujo
 de
 ejecución.
 
Consideremos
 el
 siguiente
 ejemplo,
 que
 ya
 vimos
 en
 el
 tema
 anterior:
 

1. Llamadas
 a
 funciones
 

1 /*
 
2
 *
 File:
 SquareRoot.java
 
3
 *
 -­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐
 
4
 *
 This
 program
 calculates
 the
 square
 root
 of
 a
 
5
 *
 given
 positive
 integer
 
6
 */
 
7
 
8 import
 acm.program.ConsoleProgram;
 
9
 
10 public
 class
 SquareRoot
 extends
 ConsoleProgram
 {
 
11
 
12
 
 public
 int
 squareRoot(int
 n)
 {
 
13
 
 
 
 int
 lower
 =
 0;
 
14
 
 
 
 while
 ((lower
 +
 1)
 *
 (lower
 +
 1)
 <=
 n)
 {
 
15
 
 
 
 
 
 lower
 =
 lower
 +
 1;
 
16
 
 
 
 }
 
17
 
 
 
 return
 lower;
 
18
 
 }
 
19
 
20
 
 public
 void
 run()
 {
 
21
 
 
 
 int
 n
 =
 readInt("Enter
 a
 natural
 number:
 ");
 
22
 
 
 
 int
 root
 =
 squareRoot(n);
 
23
 
 
 
 println("The
 root
 is
 "
 +
 root);
 
24
 
 }
 
25 }
 

Lo
 que
 vamos
 a
 considerar
 ahora
 es
 cómo
 se
 ejecutan
 las
 líneas,
 en
 
función
 de
 las
 llamadas
 entre
 funciones:
 
• La
 ejecución
 comienza
 la
 línea
 21,
 que
 contiene
 la
 llamada
 a
 la
 
función
 readInt.
 Se
 congela
 la
 ejecución
 del
 método
 run
 y
 se
 
ejecuta
 el
 código
 de
 readInt
 
• Poco
 podemos
 decir
 de
 la
 ejecución
 de
 readInt
 ya
 que
 no
 
disponemos
 de
 su
 código,
 pero
 a
 grandes
 rasgos,
 después
 de
 
escribir
 el
 mensaje
 y
 esperar
 la
 entrada
 del
 usuario,
 una
 vez
 éste
 
ha
 entrado
 un
 número
 entero,
 se
 devuelve
 la
 ejecución
 a
 la
 línea
 
J.M.
 Gimeno
 y
 J.L.
 González
 
2
 


 

Programación
 2
 
Recursividad
 

 

 
21
 (en
 la
 que
 habíamos
 congelado
 la
 ejecución),
 asignando
 el
 
valor
 devuelto
 por
 readInt
 a
 n
 
• La
 ejecución
 pasa
 entonces
 a
 la
 línea
 22,
 dónde
 se
 llama
 al
 
método
 squareRoot.
 Se
 vuelve
 a
 congelar
 la
 ejecución
 de
 run
 y
 
se
 pasa
 a
 ejecutar
 la
 línea
 13
 
• Después
 de
 unas
 cuantas
 vueltas
 (dependiendo
 del
 valor
 de
 n)
 ,
 
se
 sale
 del
 bucle
 y
 se
 ejecuta
 la
 línea
 17,
 volviendo
 al
 punto
 
dónde
 nos
 habíamos
 congelado
 la
 ejecución
 de
 run.
 
• …
 
¿Qué
 pasaría
 si,
 desde
 una
 función,
 llamáramos
 a
 la
 propia
 función?
 
Pues
 que
 el
 punto
 de
 ejecución
 pasaría
 a
 la
 primera
 instrucción
 de
 la
 
función
 y
 que,
 cuando
 dicha
 llamada
 retornase,
 continuaríamos
 la
 
ejecución
 en
 el
 punto
 en
 el
 que
 nos
 hubiéramos
 quedado.
 

J.M.
 Gimeno
 y
 J.L.
 González
 


 

3
 

Recursividad
 

2. Pensar
 recursivamente:
 Los
 textos
 palíndromos
 


 
Programación
 2
 

 
Una
 palabra
 (o
 texto)
 es
 palíndroma
 si
 se
 lee
 igual
 de
 izquierda
 a
 
derecha
 que
 de
 derecha
 a
 izquierda.
 
Por
 ejemplo:
 “Dábale
 arroz
 a
 la
 zorra
 el
 abad”
 es,
 tal
 y
 como
 podéis
 
comprobar,
 un
 texto
 palíndromo1
 
Lo
 que
 queremos
 será
 un
 programa
 tal
 que,
 dado
 un
 texto,
 nos
 diga
 si
 
es
 palíndromo
 o
 no.
 
El
 programa
 principal
 básicamente
 consistirá
 en:
 
• Pedir
 los
 datos
 al
 usuario.
 Como
 se
 tratará
 de
 un
 texto,
 la
 forma
 
natural
 de
 hacerlo
 será
 con
 el
 método
 readLine
 
• Eliminar
 los
 espacios
 de
 la
 cadena
 de
 entrada.
 Para
 ello
 
crearíamos
 un
 método
 removeSpaces
 tal
 que,
 dado
 un
 String,
 
devuelva
 otro,
 con
 los
 espacios
 borrados2.
 
• Llamar
 a
 la
 función
 que
 comprueba
 si
 el
 texto
 entrado
 es
 
palíndromo.
 Llamaremos
 a
 esta
 función
 isPalindrome,
 y
 será
 
una
 función
 que
 recibirá
 como
 parámetro
 un
 String
 y
 devolverá
 
un
 boolean.
 
• Finalmente,
 dependiendo
 del
 valor
 devuelto
 por
 la
 función
 
anterior,
 se
 indicará
 si
 el
 texto
 es
 palíndromo
 o
 no.
 
Si
 escribimos
 esto
 en
 Java,
 tendremos:
 


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
 Para
 simplificar,
 al
 introducir
 el
 texto
 obviaremos
 los
 posibles
 acentos
 
ortográficos
 que
 pudieran
 tener
 las
 palabras.
 
2
 Para
 programarlo
 os
 podéis
 inspirar
 en
 el
 método
 removeVocals
 del
 tema
 
anterior.
 
J.M.
 Gimeno
 y
 J.L.
 González
 

 

4
 

Programación
 2
 

 


 

Recursividad
 

1 /*
 CheckPalindrome.java
 
2
 *
 -­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐
 
3
 *
 Checks
 whether
 the
 entered
 text
 is
 palindrome.
 
4
 */
 
5
 
 
6 import
 acm.program.ConsoleProgram;
 
7
 
 
8 public
 class
 CheckPalindrome
 extends
 ConsoleProgram
 {
 
9
 
 
10
 
 public
 String
 removeSpaces(String
 text)
 {
 
11
 
 
 
 //
 Ejercicio
 
12
 
 }
 
13
 
 
 
14
 
 public
 boolean
 isPalindrome(String
 text)
 {
 
15
 
 
 
 
 //
 Se
 detallará
 más
 adelante
 
16
 
 }
 
17
 
 
18
 
 public
 void
 run()
 {
 
19
 
 
 
 String
 text
 =
 readLine(“Enter
 text
 to
 check:
 “);
 
20
 
 
 
 text
 =
 removeSpaces(text);
 
21
 
 
 
 if
 (
 isPalindrome(text)
 )
 {
 
22
 
 
 
 
 
 println(“Text
 is
 palindrome.”);
 
23
 
 
 
 }
 else
 {
 
24
 
 
 
 
 
 println(“Text
 is
 not
 palindrome.”);
 
25
 
 
 
 }
 
26
 
 }
 
27 }
 
Una
 solución
 iterativa
 

Antes
 de
 intentar
 solucionar
 el
 problema
 de
 forma
 recursiva,
 vamos
 a
 
ver
 cómo
 procederíamos
 a
 hacerlo
 con
 los
 conocimientos
 que
 tenemos,
 
es
 decir,
 mediante
 una
 solución
 iterativa.
 
¿Qué
 es
 lo
 que
 hemos
 de
 hacer?
 Básicamente
 comprobar
 que:
 
• el
 primer
 carácter
 de
 la
 cadena
 (posición
 0)
 coincide
 con
 el
 
último
 (posición
 longitud-­‐1),
 y
 
• el
 segundo
 (posición
 1),
 coincide
 con
 el
 penúltimo
 (posición
 
longitud-­‐2),
 y
 …
 
• …
 hasta
 llegar
 a
 la
 mitad
 de
 la
 cadena3
 
Para
 ello
 haremos
 un
 bucle
 que
 vaya
 generando
 las
 parejas
 a
 
comparar.
 
 En
 el
 momento
 de
 encontrar
 dos
 caracteres
 diferentes,
 ya
 
podemos
 dar
 por
 acabada
 la
 comprobación
 (ya
 que
 sabemos
 que
 no
 lo