Programming

T03-004-01 Introducción a la recursividad (Opcional)

Enunciado

Definición

Según la wikipedia, la recursividad es la forma en la cual se específica un proceso basado en su propia definición.

El árbol que se muestra a continuación es un árbol recursivo, ya que cada rama es, a su vez el inicio de otro árbol.

recursive tree

En programación se dice que una función recursiva es aquella que se llama a sí misma.

 

Ejemplo

En un ejercicio anterior, se pidió la realización de una función que calculara el factorial de un número. Una posible solución utilizando la programación imperativa es la siguiente:

    static double factorial (int numero){
        double resultado = 1;
        
        if (numero <= 0) {
            resultado = 1;
        } else {
            for (int i = 1; i <= numero; i++) {
                resultado = resultado * i;
            }
        }
        return resultado;
    }

En realidad, el cálculo del factorial de un número también se puede expresar de la siguiente forma:

Como podemos observar, el factorial de n se puede calcular en función del factorial de n-1. Por lo tanto, el ejercicio anterior se podría resolver como:

    static double factorial (int numero){
        double resultado = 1;
        
        if (numero <= 0) {
            resultado = 1;
        } else {
            resultado = numero * factorial(numero - 1);
        }
        return resultado;
    }

Ventajas e inconvenientes

Ventajas:

  • El diseño de una función recursiva es más fácil de realizar.
  • Se facilita la lectura.
  • El código es más breve.

Inconvenientes:

  • Es menos eficiente que su equivalente imperativo.
  • Consume más memoria.

Ejercicio

Realiza una aplicación que calcule los productos de dos números naturales introducidos por teclado, utilizando para ello la función recursiva multiplica(multiplicando, multiplicador).

El programa terminará cuando alguno de los dos operandos sea menor o igual que 0.

Solución


											
package javaapplication4;

import java.util.Scanner;

public class JavaApplication4 {

    public static void main(String[] args) {
        int multiplicador, multiplicando;
        Scanner sc = new Scanner(System.in);
        do {
            multiplicando = sc.nextInt();
            multiplicador = sc.nextInt();
            if (multiplicador > 0 && multiplicando > 0) {
                System.out.println(multiplicando + " x " + multiplicador + " = " + multiplica(multiplicando, multiplicador));
            }
        } while (multiplicador > 0 && multiplicando > 0);
    }

    static int multiplica(int multiplicando, int multiplicador) {
        int resultado;
        if (multiplicador == 1) {
            resultado = multiplicando;
        } else {
            resultado = multiplicando + multiplica(multiplicando, multiplicador - 1);
        }
        return resultado;
    }

}

Input

3 2
6 8
7 5
0 3
3 2
7 5
6 8
0 3

Output

3 x 2 = 6
6 x 8 = 48
7 x 5 = 35

3 x 2 = 6
7 x 5 = 35
6 x 8 = 48