Recursividad
En este post trataré los conceptos básicos de la recursividad enfocada a un lenguaje de programación, así como ejemplos muy sencillos que ayudaran a comprender la forma en que se desarrolla un método recursivo, seguiré actualizando la informacion con mas ejemplos esto no es todo.
Definición:. Se habla de recurrente o recursivo cuando un proceso es realizado un numero de veces indefinido, es decir la cantidad de veces que se repite el mismo proceso es desconocido, o puede ser infinito.
La recursividad es una alternativa diferente para implementar estructuras de repetición (ciclos). Los módulos se hacen llamadas recursivas (se implementa el método dentro de si mismo)
La Matrushka es una muñeca de madera que contiene otra muñeca más pequeña dentro de sí. Esta muñeca, también contiene otra muñeca dentro. Y así, una dentro de otra.
Matrushka
Ejemplo 1
Implementación de un método recursivo
#include<stdio.h>
void recursivo(){
printf("Ejemplo #1" ) ;
recursivo();
}
void main(){
recursivo();
}
En este ejemplo se cae en un bucle infinito, el metodo "recursivo" imprime un mensaje en pantalla e inmediatamente se vuelve a llamar al mismo metodo con lo cual ese bloque de instrucciones jamas termina ya que entre cada mensaje siempre la siguiente linea es una llamada recursiva
Ejemplo 2
Implementación de un método recursivo recibiendo un entero como parámetro y disminuyendolo entre cada llamada
#include<stdio.h>
void recursivo2(int x){
printf("%dn",x);
recursivo2(x-1);
}
void main(){
recursivo2(10);
}
Salida: 10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3.....
Casos base
En los dos ejemplos anteriores se desarrollaron métodos recursivos en los cuales la ultima linea del método era una llamada asi mismo, con lo cual el método comenzaría otra vez desde su primera instrucción hasta llegar a la penúltima linea donde el método volvía a ser llamado y comenzaría nuevamente.
Se pueden evitar estos bucles infinitos con casos bases dentro del mismo método.
Ejemplo 3
Imprimir una serie numérica comenzando desde el numero 1 hasta el valor recibido en el método
#include<stdio.h>
void serie(int x){
if(x>0){
serie(x-1);
printf("%d ",x);
}
}
void main(){
serie(10);
}
En este ejemplo el caso base (en donde se rompe la recursion) es el numero 0, en cada llamada del metodo se crea una variable diferente, aunque el nombre sea el mismo es una variable diferente que se guarda en la pila, es decir que tendremos 20 variables "x", en este ejemplo los enteros que se almacenan en la pila van de forma descendiente, 10,9,8,7,6,5,4,3,2,1 cuando se recibe como parametro el numero 0 en la llamada recursiva x-1 se llega al caso base, y se ejecutan las demas instrucciones que quedaron pendientes despues de la llamada recursiva, en este caso el printf que imprime la variable x. Pero aqui se crearon 20 copias de la variable x en la pila, siendo la ultima el numero 1, asi esta la pila 10,9,8,7,6,5,4,3,2,1 entonces el printf nos imprimira la ultima copia en haber entrado osea el numero 1, seguido del 2, el 3 asi sucesivamente hasta llegar al numero 20
"En una pila el primer objeto en entrar es el ultimo en salir, y el ultimo en entrar es el primero en salir". Asi como en una torre de CD'S
Elementos de un método recursivo
Para definir una función en forma recursiva es necesario especificar:
-Caso(s) base: Donde la recursividad se detiene
-Paso de recursión: Como se define un elemento distinto del base, en términos de elementos anteriores.
Caso Recursivo
Es una solución que involucra volver a utilizar la función original, con parámetros que se acercan más al caso base. Los pasos que sigue el caso recursivo son los siguientes:
1.-El procedimiento se llama a sí mismo
2.-El problema se resuelve, resolviendo el mismo problema pero de tamaño menor
3.-La manera en la cual el tamaño del problema disminuye asegura que el caso base eventualmente se alcanzará
el paso numero 2 del caso recursivo nos dice que el problema se resuelve resolviendo el mismo problema pero de menor tamamaño
5!=4!
4!=3!
3!=2!
2!=1!
El factorial de 5 se resuelve resolviendo el factorial de 4 y este resolviendo el de 3 y este el de 2 y este el de 1
5! = ?
..5! = 5*4!
....4! = 4*3!
......3! = 3*2!
........2! = 2*1!
..........1! = 1
Caso base = 1
#include<stdio.h>
int f(int x){
if(x==1)
return 1;
else
return x*f(x-1);
}
void main(){
printf("%d",f(5));
}
f(5) = ?......................................f (5) =120
..f(5) = 5*f(5-1)............................f (5) = 5*24 =120
....f(4) = 4*f(4-1)..........................f (4) = 4*6 = 24
......f(3) = 3*f(3-1)........................f (3) = 3*2 = 6
........f(2) = 2*f(2-1)......................f (2) = 2*1 = 2
..........f(1) = 1.............................f (1) = 1
En este post trataré los conceptos básicos de la recursividad enfocada a un lenguaje de programación, así como ejemplos muy sencillos que ayudaran a comprender la forma en que se desarrolla un método recursivo, seguiré actualizando la informacion con mas ejemplos esto no es todo.
Definición:. Se habla de recurrente o recursivo cuando un proceso es realizado un numero de veces indefinido, es decir la cantidad de veces que se repite el mismo proceso es desconocido, o puede ser infinito.
La recursividad es una alternativa diferente para implementar estructuras de repetición (ciclos). Los módulos se hacen llamadas recursivas (se implementa el método dentro de si mismo)
La Matrushka es una muñeca de madera que contiene otra muñeca más pequeña dentro de sí. Esta muñeca, también contiene otra muñeca dentro. Y así, una dentro de otra.
Matrushka
Ejemplo 1
Implementación de un método recursivo
#include<stdio.h>
void recursivo(){
printf("Ejemplo #1" ) ;
recursivo();
}
void main(){
recursivo();
}
En este ejemplo se cae en un bucle infinito, el metodo "recursivo" imprime un mensaje en pantalla e inmediatamente se vuelve a llamar al mismo metodo con lo cual ese bloque de instrucciones jamas termina ya que entre cada mensaje siempre la siguiente linea es una llamada recursiva
Ejemplo 2
Implementación de un método recursivo recibiendo un entero como parámetro y disminuyendolo entre cada llamada
#include<stdio.h>
void recursivo2(int x){
printf("%dn",x);
recursivo2(x-1);
}
void main(){
recursivo2(10);
}
Salida: 10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3.....
Casos base
En los dos ejemplos anteriores se desarrollaron métodos recursivos en los cuales la ultima linea del método era una llamada asi mismo, con lo cual el método comenzaría otra vez desde su primera instrucción hasta llegar a la penúltima linea donde el método volvía a ser llamado y comenzaría nuevamente.
Se pueden evitar estos bucles infinitos con casos bases dentro del mismo método.
Ejemplo 3
Imprimir una serie numérica comenzando desde el numero 1 hasta el valor recibido en el método
#include<stdio.h>
void serie(int x){
if(x>0){
serie(x-1);
printf("%d ",x);
}
}
void main(){
serie(10);
}
En este ejemplo el caso base (en donde se rompe la recursion) es el numero 0, en cada llamada del metodo se crea una variable diferente, aunque el nombre sea el mismo es una variable diferente que se guarda en la pila, es decir que tendremos 20 variables "x", en este ejemplo los enteros que se almacenan en la pila van de forma descendiente, 10,9,8,7,6,5,4,3,2,1 cuando se recibe como parametro el numero 0 en la llamada recursiva x-1 se llega al caso base, y se ejecutan las demas instrucciones que quedaron pendientes despues de la llamada recursiva, en este caso el printf que imprime la variable x. Pero aqui se crearon 20 copias de la variable x en la pila, siendo la ultima el numero 1, asi esta la pila 10,9,8,7,6,5,4,3,2,1 entonces el printf nos imprimira la ultima copia en haber entrado osea el numero 1, seguido del 2, el 3 asi sucesivamente hasta llegar al numero 20
"En una pila el primer objeto en entrar es el ultimo en salir, y el ultimo en entrar es el primero en salir". Asi como en una torre de CD'S
Elementos de un método recursivo
Para definir una función en forma recursiva es necesario especificar:
-Caso(s) base: Donde la recursividad se detiene
-Paso de recursión: Como se define un elemento distinto del base, en términos de elementos anteriores.
Caso Recursivo
Es una solución que involucra volver a utilizar la función original, con parámetros que se acercan más al caso base. Los pasos que sigue el caso recursivo son los siguientes:
1.-El procedimiento se llama a sí mismo
2.-El problema se resuelve, resolviendo el mismo problema pero de tamaño menor
3.-La manera en la cual el tamaño del problema disminuye asegura que el caso base eventualmente se alcanzará
el paso numero 2 del caso recursivo nos dice que el problema se resuelve resolviendo el mismo problema pero de menor tamamaño
5!=4!
4!=3!
3!=2!
2!=1!
El factorial de 5 se resuelve resolviendo el factorial de 4 y este resolviendo el de 3 y este el de 2 y este el de 1
5! = ?
..5! = 5*4!
....4! = 4*3!
......3! = 3*2!
........2! = 2*1!
..........1! = 1
Caso base = 1
#include<stdio.h>
int f(int x){
if(x==1)
return 1;
else
return x*f(x-1);
}
void main(){
printf("%d",f(5));
}
f(5) = ?......................................f (5) =120
..f(5) = 5*f(5-1)............................f (5) = 5*24 =120
....f(4) = 4*f(4-1)..........................f (4) = 4*6 = 24
......f(3) = 3*f(3-1)........................f (3) = 3*2 = 6
........f(2) = 2*f(2-1)......................f (2) = 2*1 = 2
..........f(1) = 1.............................f (1) = 1