Recursividad¶

Un método recursivo es un método que se llama a sí mismo. Un método iterativo es un método que usa un bucle para repetir una acción. En cierto sentido, la recursividad es una alternativa a las estructuras de control iterativas (en bucle).

public void holaIterativo(int n){
    for (int i = 0; i < n; i++){
        System.out.println("Hola");
    }
}

public void holaRecursivo(int n){
    if (n > 0){
        System.out.println("Hola");
        holaRecursivo(n-1); // Llamada recursiva
    }
}

En el ejemplo anterior, es mucho menos eficiente llamar a un método cinco veces que repetir un bucle for cinco veces. Las llamadas a métodos ocupan más memoria que los bucles e implican más sobrecarga computacional, en tareas como pasar parámetros, asignar almacenamiento para las variables locales del método y devolver los resultados del método.

Sobre eficiencia

Los algoritmos y métodos iterativos son generalmente más eficientes que los algoritmos recursivos que hacen lo mismo.

Recursividad como un enfoque de resolución de problemas

Dado que la recursividad no es realmente necesaria, si un lenguaje de programación tiene bucles, y no es más eficiente que los bucles, ¿por qué es tan importante?

Porque la recursividad es un enfoque eficaz para la resolución de problemas. Es una forma de ver un problema.

La recursividad se basa en dos conceptos clave de resolución de problemas: "divide y vencerás" y "auto-similaridad".

Parte recursiva y caso base¶

Una definición recursiva consta de dos partes: una parte recursiva que se repite y reduce el problema en una versión más pequeña del problema original, y un caso base o límite no recursivo, que define una condición límite y se utiliza para detener la recursividad.

Veamos un ejemplo con el cálculo de un factorial de n! Recordamos como se hacía el cálculo de n!: n! = n * (n-1) * n(n-2) * .... mientras n > 0. Además, 0! se define como 1.

Ejemplos:

4! = 4 * 3 * 2 * 1 = 24
3! = 3 * 2 * 1 = 6
1! = 1
0! = 1

Como vemos en el ejemplo, podemos deducir que el factorial se repite en términos de (n-1) y el único caso donde no se calcula el factorial es 0!, esto nos lleva a que:

n! = 1 --> if n = 0 //caso base
n! = n * (n-1) --> if n > 0 //caso recursivo

De forma que el factorial de un número quedaría codificado de la siguiente forma:

public int factorial(int n){
    if (<=0){
        return 1;
    }else{
        return n * factorial(n-1);
    }
}

Actividades¶

AC 409 (RA2 / CE2b, CE2d, CE2e, CE2f, CE2i / IC1 / 3p). Realiza un programa que solicite la base de una potencia y el exponente. Has de resolverlo de manera recursiva.
AC 410 (RA2 / CE2b, CE2d, CE2e, CE2f, CE2i / IC1 / 3p). Has de realizar un programa que muestra los N primeros números de la sucesión de Fibonacci de forma recursiva. Ejemplo de los primeros números de Fibonacci: 0,1,1,2,3,5,8,13,21,34…

Es obligatorio el uso de métodos y comentarios en javadoc para obtener la máxima puntuación del ejercicio.
PR 411 (RA2 / CE2b, CE2d, CE2e, CE2f, CE2i / IC2 /5p). Realiza un programa que te ayude a resolver el juego de las Torres de Hanoi de manera recursiva.
Las torres de Hanoi

Las Torres de Hanoi es un juego oriental que consta de tres columnas llamadas origen, destino y auxiliar y una serie de discos de distintos tamaños. Los discos están colocados de mayor a menor tamaño en la columna origen. El juego consiste en pasar todos los discos a la columna destino y dejarlos como estaban de mayor a menor. (el más grande en la base, el más pequeño arriba)

Las reglas del juego son las siguientes:
- Sólo se puede mover un disco cada vez.
- Para cambiar los discos de lugar se pueden usar las tres columnas.
- Nunca deberá quedar un disco grande sobre un disco pequeño.
En este caso haremos que los discos sean números generados aleatoriamente del 1 al 9. Trabajaremos con 4 discos
Es obligatorio el uso de métodos y comentarios en javadoc para obtener la máxima puntuación del ejercicio.