La recursividad es una función que se llama a sí misma para dividir un problema en problemas más sencillos, el método recursivo debe estar compuesto de una caso base para el cual ya se conoce un resultado y una llamada al mismo método con una versión ligeramente más sencilla del problema inicial
ejemplo 1, factoriales:
Para todo n entero natural, se llama factorial n (n!) al producto de todos los enteros entre 1 y n:
| n | n! | ||
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 2 × 1 | = 2 × 1! | = 2 |
| 3 | 3 × 2 × 1 | = 3 × 2! | = 6 |
| 4 | 4 × 3 × 2 × 1 | = 4 × 3! | = 24 |
| 5 | 5 × 4 × 3 × 2 × 1 | = 5 × 4! | = 120 |
| 6 | etc | etc |
Código:
1 2 3 4 5 6 | public void factoriales(long n){ if(n==1) return 1; else return n*factoriales(n-1);} |
El método factoriales se llama a sí mismo disminuyendo cada vez el numero inicial en una unidad hasta que llega a valer 1 y por lo tanto alcanza el caso base, en ese momento se devuelven todas las llamadas recursivas realizas al método factoriales retornando el valor del actual multiplicado por el valor anterior.
ejemplo 2, Fibonachi:
La sucesion de Fibonachi comienza por 0 y 1, y cada numero siguiente es la
suma de los dos anteriores:
0,1,1,2,3,5,8,13,21,34,55,89
Código:
1 2 3 4 5 6 7 | public void fibonachi(long n){ if(n==0 || n==1) return n; else return fibonachi(n-2)+fibonachi(n-1);} |
Este método esta compuesto de dos casos bases, y de dos llamadas recursivas al método, a esto se le denomina recursividad mútliple, a diferencia del método factoriales que sólo hace una llamada recursiva y se denomina recursividad simple. En ambos casos es de tipo directa, también es posible efectuar recursión indirectamente: una método puede llamar a otro quien, a su vez, acabe llamando al primero.
A continuación se expone un ejemplo de programa que utiliza recursión indirecta, y nos dice si un número es par o impar. Al igual que el programa anterior, hay otro método mucho más sencillo de determinar si un número es par o impar, basta con determinar el resto de la división entre dos. Por ejemplo: si hacemos par(2) devuelve 1 (cierto). Si hacemos impar(4) devuelve 0 (falso).
Código:
1 2 3 4 5 6 7 8 9 10 11 | int par(int n){ if (n == 0) return 1; return impar(n-1);}int impar(int n){ if (n == 0) return 0; return par(n-1);} |
Código:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | int x[]={7,3,4,6,8,9,5}; int n = 7; // Enviamos datos max(n, x); public static int max(int n, int x[]) { if(n == 1) return x[0]; if (x[n-1] > max(n-1, x)) return x[n-1]; else return max(n-1, x); } |
Hay que apuntar que el factorial puede obtenerse con facilidad sin necesidad de emplear funciones recursivas, es más, el uso del programa anterior es muy ineficiente, pero es un ejemplo muy claro.
Dado un array constituido de números enteros, devolver la suma de todos los elementos. En este caso se desconoce el número de elementos. En cualquier caso se garantiza que el último elemento del array es -1, número que no aparecerá en ninguna otra posición.
Código:
1 2 3 4 5 6 7 8 9 | private static int sumaArray2(int vector[], int n){ if(n==-1)return 0; else return vector[n]+ sumaArray2(vector, n-1); }static int []array={1,2,3,4,5,6};System.out.println(sumaArray2(array,array.length-1)); |
Dado un array constituido de números enteros y que contiene N elementos siendo N >= 1, devolver el elemento mayor.
Código:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | static int []array={510,41,300,4,25,6}; private static int mayor(int vector[], int n){ int aux; if(n==-1)return 0; else{ aux = mayor(vector, n-1); if(vector[n]>aux) return vector[n]; else return aux; } } System.out.println(mayor(array,array.length-1)); |
máximo comun divisor.
Código:
1 2 3 4 5 6 7 8 9 10 | private static long mcd(long a, long b){ if(b==0) return a; else return mcd(b,a%b); } System.out.println(mcd(80,25));resultado 5; |
Video utilizando Recursividad
No hay comentarios:
Publicar un comentario