Teniendo en cuenta que la recursividad no es una estructura de datos, sino que es una técnica de programación que nos permite que una instrucciones se ejecuta n veces,esto reemplaza muchas veces a estructuras repetitivas.
En programación se llama recursividad a los métodos que tiene la propiedad de llamarse así mismo, se utiliza la recursividad como alternativa a la iteración.
MÉTODO RECURSIVO: Un método es recursivo si se llama así mismo directo o indirectamente. En recursión directa el método p() posee una sentencia que invoca a p(), en cuanto a la recursión indirecta el método p() invoca a un método m() y este a un método n(), y así hasta invocar al método p() nuevamente.
Características de la recursividad
Caso trivial o fin de la recursión: Un requisito para que un método sea recursivo es que debe tener una condición de salida, no debe generar una secuencia infinita de invocación así mismo. A la condición de salida se la denomina base.
Parte recursiva: Es la parte que hace que el método se llame así mismo, normalmente con el valor de parámetros que cambian en cada llamada.
Ventajas y desventajas.
Ventajas: En este caso no es necesario definir la secuencia de pasos exacta para resolver el problema, son programas cortos.
Desventajas: Podría ser menos eficiente, Creación de muchas variables, Puede necesitar mucha memoria.
Ejemplos:
Factorial de un numero:
1. Encontrar el factorial de un número natural Como podemos ver en el método se debe ingresar el numero n, y la condición para que termine la recursividad es que n sea igual a 0, si no es así se ejecuta la parte recursiva n*(factorial(n-1)); la cual en cada repetición disminuye un número.
Caso base: if(n==0) y retorna 1 ya que el factorial de 0 es 1.
Parte recursiva: n*(factorial(n-1));
Supongamos que n es 4, entonces la primera condición if (n==0) no se ejecuta, y se ejecuta la parte recursiva. Fac (4) 4*3*2*1=24 4*fac (3) 3*fac(2)…etc. Esto se ejecuta hasta que la condición base sea verdadera, y luego se van resolviendo cada uno de los factoriales hasta que retorna 24 que es la solución.
2. Obtener el Nésimo término de la serie de Fibonacci
Al igual que el ejercicio anterior tiene una condición de salida en este caso es if ((n == 0) || (n == 1)) y la parte recursiva es fibonacci (n-1) + fibonacci(n-2); Si el número es n es 7 se produce un árbol y divide el problema es dos como lo vemos fib(6) y fib(5), y así hasta llegar al caso base, el problema que si es un numero grande ocupa mucho espacio de memoria ya que genera muchos árboles.
3. Suma de N números naturales
Caso base: if (n==1)
Parte recursiva: 1+ sumaN(a, n-1);
La solución recursiva se basa en lo siguiente:
Caso Base: Si n == 1 la suma es 1 Si n > 1 La suma es n + (la suma de los anteriores números hasta 1) Por ejemplo supongamos que, si n = 5, la suma es 5 más la suma desde 1 hasta 4. A su vez la suma si n = 4 es 4 + la suma desde 1 hasta 3 y así sucesivamente hasta llegar al caso base.
4. División entre dos números enteros mediante restas sucesivas
Como sabemos no se puede dividir para cero ningún número por lo cual hacemos de esto el caso base por lo que si el dividendo es cero retorna cero esa es la condición de salida y la parte recursiva es la siguiente 1 + division(a - b, b); Caso Base: Si el dividendo es menor que el divisor el cociente es cero. Caso contrario, se restan el dividendo y el divisor. Al resultado se le vuelve a restar el divisor. Esta resta se repite mientras se pueda realizar, o sea, mientras el resultado sea mayor o igual que el divisor. El número de veces que se ha hecho la resta es el cociente. Con un ejemplo lo veremos más claro. Por ejemplo, para dividir 10 entre 3 haríamos: 10 - 3 = 7 7 - 3 = 4 4 - 3 = 1 No se puede seguir restando ya que el último valor obtenido (1) es menor que el divisor. Como se han realizado 3 restas el cociente es 3.
5. Invertir un número.
Entrada: 123 Salida: 321 Si es un solo número ingresado no podemos invertirlo por lo cual si núm. es igual a uno esta situación termina la recursión, y el código recursivo es inverNum (num.substring (1)) + num.charAt (0); Caso base: num.length()-1 Parte recursiva: inverNum(num.substring(1)) + num.charAt (0);
RECURSIVIDAD DE LOS MÉTODOS DE UNA LISTA ENLAZADA SIMPLE
En este caso los métodos recursivos de la lista enlaza realizados son impresión de datos, buscar el último dato, y búsqueda de datos en la lista. Como sabemos las listas enlazadas están formadas por nodos y estos se unen mediante enlaces.
Se utilizaran las 3 formas de ingreso de datos.
Métodos recursivos de la lista
Buscar último nodo de la lista:
En el caso de buscar el ultimo nodo, como podemos ver se ha creado un método ultimobuscar() este método esta, es el que invoca al método recursivo, y a su vez inicializa la cabecera de la lista. En segundo método ultimo() que tiene un parámetro de entrada posee la condición de parada o caso base y es donde se imprime el último dato de la lista, si esta condición no se cumple se ejecuta la parte recursiva, como podemos ver el método se invoca varias veces hasta encontrar el último dato de la lista.
Buscar un nodo de la lista:
Es muy parecido al anterior método solo que esta vez se debe ingresar un parámetro a buscar, como vemos el caso base se cumple cuando el dato a buscar es igual al dato que tiene la lista.
Imprimir un nodo de la lista:
Como ya conocemos en una lista enlazada para imprimir sus datos es necesario recorrer toda la lista. Para hacerlo de forma iterativa la condición para recorrer la lista en que la variable n sea null, para hacerlo de forma recursiva utilizaremos la misma condición. Se creara un método ver donde se creara la variable p al cual se le asignara la cabecera de la lista (cab) y llamaremos al método recorrido que es el recursivo al cual le asignaremos la cabecera (p). Este método tiene similitud con los anteriores debido a que se utiliza el mismo método que invoca al método recursivo, el método recorrido tiene un parámetro p y la condición de parada es hasta que p sea null, mientras tanto con cada invocación se van mostrando los datos de la lista.
En programación se llama recursividad a los métodos que tiene la propiedad de llamarse así mismo, se utiliza la recursividad como alternativa a la iteración.
MÉTODO RECURSIVO: Un método es recursivo si se llama así mismo directo o indirectamente. En recursión directa el método p() posee una sentencia que invoca a p(), en cuanto a la recursión indirecta el método p() invoca a un método m() y este a un método n(), y así hasta invocar al método p() nuevamente.
Características de la recursividad
Caso trivial o fin de la recursión: Un requisito para que un método sea recursivo es que debe tener una condición de salida, no debe generar una secuencia infinita de invocación así mismo. A la condición de salida se la denomina base.
Parte recursiva: Es la parte que hace que el método se llame así mismo, normalmente con el valor de parámetros que cambian en cada llamada.
Ventajas y desventajas.
Ventajas: En este caso no es necesario definir la secuencia de pasos exacta para resolver el problema, son programas cortos.
Desventajas: Podría ser menos eficiente, Creación de muchas variables, Puede necesitar mucha memoria.
Ejemplos:
Factorial de un numero:
1. Encontrar el factorial de un número natural Como podemos ver en el método se debe ingresar el numero n, y la condición para que termine la recursividad es que n sea igual a 0, si no es así se ejecuta la parte recursiva n*(factorial(n-1)); la cual en cada repetición disminuye un número.
Caso base: if(n==0) y retorna 1 ya que el factorial de 0 es 1.
Parte recursiva: n*(factorial(n-1));
Supongamos que n es 4, entonces la primera condición if (n==0) no se ejecuta, y se ejecuta la parte recursiva. Fac (4) 4*3*2*1=24 4*fac (3) 3*fac(2)…etc. Esto se ejecuta hasta que la condición base sea verdadera, y luego se van resolviendo cada uno de los factoriales hasta que retorna 24 que es la solución.
2. Obtener el Nésimo término de la serie de Fibonacci
Al igual que el ejercicio anterior tiene una condición de salida en este caso es if ((n == 0) || (n == 1)) y la parte recursiva es fibonacci (n-1) + fibonacci(n-2); Si el número es n es 7 se produce un árbol y divide el problema es dos como lo vemos fib(6) y fib(5), y así hasta llegar al caso base, el problema que si es un numero grande ocupa mucho espacio de memoria ya que genera muchos árboles.
3. Suma de N números naturales
Caso base: if (n==1)
Parte recursiva: 1+ sumaN(a, n-1);
La solución recursiva se basa en lo siguiente:
Caso Base: Si n == 1 la suma es 1 Si n > 1 La suma es n + (la suma de los anteriores números hasta 1) Por ejemplo supongamos que, si n = 5, la suma es 5 más la suma desde 1 hasta 4. A su vez la suma si n = 4 es 4 + la suma desde 1 hasta 3 y así sucesivamente hasta llegar al caso base.
4. División entre dos números enteros mediante restas sucesivas
Como sabemos no se puede dividir para cero ningún número por lo cual hacemos de esto el caso base por lo que si el dividendo es cero retorna cero esa es la condición de salida y la parte recursiva es la siguiente 1 + division(a - b, b); Caso Base: Si el dividendo es menor que el divisor el cociente es cero. Caso contrario, se restan el dividendo y el divisor. Al resultado se le vuelve a restar el divisor. Esta resta se repite mientras se pueda realizar, o sea, mientras el resultado sea mayor o igual que el divisor. El número de veces que se ha hecho la resta es el cociente. Con un ejemplo lo veremos más claro. Por ejemplo, para dividir 10 entre 3 haríamos: 10 - 3 = 7 7 - 3 = 4 4 - 3 = 1 No se puede seguir restando ya que el último valor obtenido (1) es menor que el divisor. Como se han realizado 3 restas el cociente es 3.
5. Invertir un número.
Entrada: 123 Salida: 321 Si es un solo número ingresado no podemos invertirlo por lo cual si núm. es igual a uno esta situación termina la recursión, y el código recursivo es inverNum (num.substring (1)) + num.charAt (0); Caso base: num.length()-1 Parte recursiva: inverNum(num.substring(1)) + num.charAt (0);
RECURSIVIDAD DE LOS MÉTODOS DE UNA LISTA ENLAZADA SIMPLE
En este caso los métodos recursivos de la lista enlaza realizados son impresión de datos, buscar el último dato, y búsqueda de datos en la lista. Como sabemos las listas enlazadas están formadas por nodos y estos se unen mediante enlaces.
Se utilizaran las 3 formas de ingreso de datos.
Métodos recursivos de la lista
Buscar último nodo de la lista:
En el caso de buscar el ultimo nodo, como podemos ver se ha creado un método ultimobuscar() este método esta, es el que invoca al método recursivo, y a su vez inicializa la cabecera de la lista. En segundo método ultimo() que tiene un parámetro de entrada posee la condición de parada o caso base y es donde se imprime el último dato de la lista, si esta condición no se cumple se ejecuta la parte recursiva, como podemos ver el método se invoca varias veces hasta encontrar el último dato de la lista.
Buscar un nodo de la lista:
Es muy parecido al anterior método solo que esta vez se debe ingresar un parámetro a buscar, como vemos el caso base se cumple cuando el dato a buscar es igual al dato que tiene la lista.
Imprimir un nodo de la lista:
Como ya conocemos en una lista enlazada para imprimir sus datos es necesario recorrer toda la lista. Para hacerlo de forma iterativa la condición para recorrer la lista en que la variable n sea null, para hacerlo de forma recursiva utilizaremos la misma condición. Se creara un método ver donde se creara la variable p al cual se le asignara la cabecera de la lista (cab) y llamaremos al método recorrido que es el recursivo al cual le asignaremos la cabecera (p). Este método tiene similitud con los anteriores debido a que se utiliza el mismo método que invoca al método recursivo, el método recorrido tiene un parámetro p y la condición de parada es hasta que p sea null, mientras tanto con cada invocación se van mostrando los datos de la lista.
No hay comentarios.:
Publicar un comentario