Recursividad
04 noviembre 2017
Laboratorio de programación Nro. 11 - Recursividad
Al finalizar esta actividad usted estará en la capacidad:
- Aplicar los conceptos fundamentales de recursividad.
- Resolver un problema aplicando recursividad.
El problema que debe resolver es el siguiente: Elabore un programa en Java que sin usar estructuras repetitivas cuente el número de dígitos que tiene un número entero. Por ejemplo:
| Entrada | Salida |
|---|---|
| 1 | 1 |
| 22 | 2 |
| 511 | 3 |
| 9876 | 4 |
Como se pudo percatar el programa debe contar cuántos digitos forman el número y presentarlos.
1. Análisis del problema
¿Cómo obtener los dígitos que forman un número?
Para comprender el problema de forma recursiva es necesario descomponerlo de la siguiente manera: se usará 9876 como ejemplo e imagine que existe un método denominado contarDigitos que devuelve el número de digitos que tiene un número.
- contarDigitos(9876) = 1 + contarDigitos(987)
- contarDigitos(987) = 1 + contarDigitos(98)
- contarDigitos(98) = 1 + contarDigitos(9)
- contarDigitos(9) = 1
Para contar el número de digitos se plantea la siguiente solución: divisiones enteras sucesivas por 10 hasta que el cociente sea 0, el número total de divisiones será igual al número de digitos que tiene un número. La siguiente imagen muestra ese proceso:
La imagen muestra que en el número 9876 existen 4 digitos, es decir se pueden hacer hasta 4 divisiones enteras por 10 hasta que el cociente es 0. No olvide que en una división entera el cociente será otro número entero.
2. Caso base y recursivo
Cuando se habla de recursividad es necesario determinar cuál es el caso base y el recursivo. El primero de ellos tiene como objetivo poner fin a la ejecución dle programa. En cambio el segundo busca que se genere una nueva iteracción.
Para el problema propuesto el caso base se encuentra en la condición que debe detener las divisiones, es decir cuando:
num / 10 == 0
Cuando se cumple esa condición, las llamadas recursivas deben detenerse. Este caso es primordial ya que evita que las llamadas recursivas sean infinitas. Sino es capaz de encontrar el caso base, es mejor que desista del uso de recursividad.
El caso recursivo, a diferencia del anterior no busca detener las iteracciones, sino que busca realizar una nueva. En nuestro problema el caso recursivo es el que se muestra a continuación:
1 + contarDigitos(num / 10)
Observe como se hace la llamada al método, pero se cambia el parámetro que recibe, esto busca cumplir con el análisis que se hizo del problema, es decir invocar nuevamente al método pero esta vez sin el último digito el mismo que ya se contó y se representa agregando una unidad.
El método completo es el siguiente:
int contarDigitos(int num) {
if(num / 10 == 0) {
return 1;
} else {
return 1 + contarDigitos(num / 10);
}
}
El programa completo se muestra a continuación, ejecútelo y vea como funciona correctamente. Además observe como se invoca al método directamente en la sentencia printf.
Si desea ejecutar el programa haga clic sobre el botón play ▶ ubicado en la parte superior. También puede modificar, compilar y ejecutar su propio código. Finalmente puede abrir el programa en el sitio repl.it haciendo clic en open in.
| Mixed with