Anuncios Google

Recursividad

Tutoriales de Programaciones

La recursividad es una tecnica de programación útil para realizar algunas tareas a la inversa. Se aplica a las funciones, pero no siempre es la manera de resolver un problema más eficiente. Aquí se expllica como utilizarla.

Recursividad ¿Qué es eso?

Antes de nada, decir que la recursividad no siempre es el mejor método para comprender la lógica ni para la eficiencia del programa, pues muchas veces se pueden realizar las operaciones de mejor manera.

Consiste en la llamada de una función a sí misma repetidas veces hasta que se cumpla una condición.

La recursividad es una técnica de programación aplicable a funciones, que se desarrolla en forma de pila. La recursividad ocurre cuando una función se llama a sí misma hasta que se cumpla una condición. La pila, quiere decir, last-in, first-out; o lo que es lo mismo, la última llamada a la función es la primera en realizarse. Hay que tener cuidado al usarla, pues si no se sabe usar bien podríamos acabar en un bucle infinito, o lo que es lo mismo, nuestro programa no acabaría. Por si esta explicacion no ha quedado clara, aquí se expone un ejemplo cuya función es escribir una frase introducida previamente por el usuario al revés.

Ejemplo

/*Código para escribir una frase al revés*/
/*Programado por P22 para Scenebeta el 24-3-10*/
 
/*Inclusión de librerias*/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
 
/*Definir la constante intro*/
#define intro '\n'
 
/*Variable externa auxiliar*/
int aux = 0;
 
int main(){
 
/*Declaración de variables*/
    void frasereves();
    char eleccion;
    int continuar;
    int pausa;
 
    printf("Presiona INTRO para comenzar");
 
/*Bucle para repetir el programa siempre que la persona lo desee*/
    do{
    getchar();
    printf("\nIntroduce una frase para escribirla al reves\n");
    frasereves();
    printf("\n\nDeseas introducir otra frase?[S/N]\n");
    scanf("%c", &eleccion);
    if ((toupper(eleccion)) == 'S') continuar = 1;
    else if ((toupper(eleccion))  == 'N') continuar = 0;
    else{
         printf("\nERROR, el caracter introducido no es un caracter valido\n");
         continuar = 0;
         }
    }while(continuar == 1); 
 
    printf("\nADIOS! Ten un buen dia...\n");
 
    scanf("%i", &pausa);
    return 0;
}
 
/*Función recursiva
Se observa que en la misma función
se realiza todo, introducción
y salida de datos*/
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}

El programa realiza muchas otras cosas aparte de escribir la frase al revés. La pide, la escribe, pregunta si se desea introducir otra y si se le dice que no, se despide.

Explicación del código

El resto del programa se da por entendido que la gente lo comprende, por lo que solo se explicará la función recursiva:

void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}

En estas nueve líneas es donde está el programa entero. Esto se explicará más detenidamente para su mejor comprensión.

 

void frasereves(){
Una función corriente sin argumentos ni valor de salida.

 

char nombre;
Declaración de la variable nombre. La etiqueta de esta variable es nombre porque está basada en un antiguo (hace 2 semanas) programa creado por mí, pero da igual nombre que scenebeta que casa que coche, todas son válidas siempre que se reemplace en los otros lugares a los que se la llame.

 

if ((nombre = getchar()) != intro ){
En est función, que puede llegar a ser de difícil comprensión para los principiantes por su forma concisa, se pide un valor para nombre y se compara con la constante intro.

Cabe destacar que se podría haber escrito de la siguiente manera:

nombre = getchar();
if (nombre != intro){

Es exactamente lo mismo pero menos conciso. Revisa el código si no lo entiendes.

 

frasereves();
Llamada recursiva a la función.

 

printf("%c",nombre);  
Muestra en pantalla el valor de nombre.

 

return;
Se pone aun siendo una función sin salida de valores porque eso es una buena táctica de programación.

 

}
Cierra la función.

 

Explicación de la lógica del programa

Bien, en sí, la técnica de la recursividad es dificil de explicar.

En primer lugar, la función if, pide un valor para la primera variable, que aunque tenga el mismo nombre es completamente distinta a las otras. Luego se compra con un carácter de nueva línea y si es distinto, vuelve a llamarse a sí misma. Por último, si es distinta, muestra el valor de nombre.

Aquí se pone una especie de interacción con el programa para entender mejor la "pila":

void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){  //Se introduce la letra 'P'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}
 
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce '2'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}
 
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce '2'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}
 
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce 'm'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}
 
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce 'o'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}
 
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce 'l'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}
 
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce 'a'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}
 
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce '\n'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}

Esto puede verse un poco largo, ahora, esto es la pila. Como la última se termina directamente pues la sentencia if no se cumple y pasa a la llamada, se ejecuta la anterior, y se van terminando continuamente el resto de funciones, pues el resto de funciones if se terminan continuamente. Y así sucesivamente se terminan. Se podría escribir de otra forma un tanto extraña, que también es extensa, aquí se muestra:

void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce la 'P'
 
 
        char nombre;
        if ((nombre = getchar()) != intro ){  //Se introduce '2'
 
 
            char nombre;
            if ((nombre = getchar()) != intro ){  //Se introduce '2'
 
 
                char nombre;
                if ((nombre = getchar()) != intro ){  //Se introduce el salto de línea '\n'
 
 
                    char nombre;
                    if ((nombre = getchar()) != intro ){ 
//Aquí iría otra pero no se pone por abreviar. La sentencia if la salta por no ser cierta
                         printf("%c",nombre);
                          }
 
 
                      printf("%c",nombre);
                      }
 
 
                  printf("%c",nombre);
                  }
 
              printf("%c",nombre);
              }
 
 
          printf("%c",nombre);
          }
return
}

A simple vista podría ser más dificil de comprender, pero seguro que con este ejemplo se termina de entender absolutamente todo mejor.

4.512195
Tu voto: Ninguno Votos totales: 4.5 (41 votos)

Anuncios Google

Comentarios

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.
Imagen de barney77

Duda

Vaya pedazo de tutorial, lo he leído como 3 veces, y aún tengo duda, la verdad me ha sido dificl comprender, y, solo para asesiorarme de que comprendí bien, todo esto;

void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){  //Se introduce la letra 'P'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}
 
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce '2'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}
 
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce '2'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}
 
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce 'm'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}
 
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce 'o'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}
 
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce 'l'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}
 
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce 'a'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}
 
void frasereves(){
    char nombre;
    if ((nombre = getchar()) != intro ){ //Se introduce '\n'
          frasereves();
          printf("%c",nombre);
          }
    else aux = 1;
    return;
}

Significa que se introdujo la frase: "p22mola\n", no?. Y la palabra se invierte porque al acabar todas las condiciones(osea cuando se introdujo "\n") vuelve a llamar a la función y termina el anterior y asi consecutivamente hasta llegar al primero, por lo que imprime los caracteres de manera inversa, o estoy mal?. Es un poco confuso S: pero estoy casi seguro de que ya lo tengo.

Un saludo, muchas gracias por estos tutoriales.

Imagen de klozz

mm tengo una duda como puedo

mm tengo una duda como puedo hacer que funcione una cadena de caracteres? osea como String? ya que con char nadamas puedo usar un caracter xD o corrijanme si me eh equivocado o como puedo hacer que char acepte mas de un caracter? un saludo espero puedan solucionar mi duda n.n


TEAM MEX Homebrew y desarrollo PSP

Metal TrooperV.Pre-Alpha (15%)Lua , 10% C .

Ubunshell VProof. (45%)C

RPG Magues (35%)Lua , 5% C


Android development for Xperia X8 ^^ mis roms en XDA-Developers ya que en Scenebeta no las publican xD

Xperience  | MIUI Pikachu | Semc debrand engine | Froyexp | Xperience walkman mod | Android 4.0.4 CN9 Crema de nieve

-- KLOZZ

Imagen de the dragon lives

Buenas

Siguiendo con los tutos de SB me toca este, esta bien eso de hacer las cosas al revés, pero, a alguien se le ocurre alguna utilidad mas ademas de para poner frases del revés? no se algo a lo que se le pueda aplicar la recursividad (ademas de a lo de las frases).

Imagen de pspgorrister

El mejor ejemplo de recursividad

La verdad es que el ejemplo de la frase, no sería lo más práctico de recursividad. Imagínate leer un directorio con sus subdirectorios en una función, tienes que usar recursividad cada vez que encuentres un directorio, ya que vuelves a llamar a la función que lee los ficheros.


LuaDiE: Crea en Lua sin teclear código. Compatible HM7, HMv2, LuaPlayer, LuaDEV y PGE.

Imagen de the dragon lives

Osea

Que seria como la acción de ir a la función anterior (mas o menos), por ejemplo, si quisiera utilizar la recursividad en una calculadora, la función de recursividad podría ser la de mostrar el resultado anterior a el ultimo resultado o sustituye al botón C de las calculadoras, ese que "borra" el ultimo valor que añades.

Imagen de Robione22

Retroalimentación.

Me he estado leyendo (otra vez) los tutos de Tanos, lo primero es que no todos están en orden, ya que el tuyo se atravesó en segundo lugar XD, pero yo lo deje hasta el final.

Te dejo un par de comentarios.

Primero, estuve siguiendo el tuto (y tal como Tanos lo dejó dicho) he escrito el código en el Dev C++, he modificado comentarios, bueno el punto es que al dar F9 e intentar compilar, me ha marcado un error en esta línea: if ((toupper(eleccion)) == 'S') continuar = 1;

Después me fueron saltando error tras error y me dí a la tarea de tratar de corregirlos, el punto es que así me quedó el código corregido (no totalmente):

<textarea name="code" class="c" language="c">//Recursividad
 
//Directivas
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
 
//Variables y Constantes
#define intro '\n'
 
int aux = 0;
 
//Bucle principal
int main()
{
    void frasereves();
    char eleccion;
    int continuar;
    int pausa;
 
    printf("Presiona ENTER para comenzar");
 
    do
    {
                     getchar();
                     printf("\nIntroduce una frase para escribirla al reves: \n");
                     frasereves();
                     printf("\n\nDeseas introducir otra frase?[S/N] \n");
                     scanf("%c",&eleccion);
                     if ((toupper(eleccion)) == 'S')
                     {
                                  continuar = 1;
                     }
                     else if ((toupper(eleccion)) == 'N') 
                     {
                          continuar = 0;
                     }
                     else
                     {
                         printf("\nERROR, el caracter introducido no es un caracter valido\n");
                         continuar = 0;
                     }
    }
    while (continuar == 1);
    {
          printf("\nADIOS! Ten un buen dia...\n");
          scanf("%i",&pausa);
    }
    return 0;
}
 
//Funcion Recursiva
void frasereves()
{
     char nombre;
     if((nombre = getchar()) != intro)
     {
                frasereves();
                printf("%c",nombre);
     }
 
     else aux = 1;
     return;
}
//Recursividad

//Directivas
#include <stdio.h>
#include <stdlib.h>

//Variables y Constantes
#define intro '\n'

int aux = 0;

//Bucle principal
int main()
{
void frasereves();
char eleccion;
int continuar;
int pausa;

printf("Presiona ENTER para comenzar");

do
{
getchar();
printf("\nIntroduce una frase para escribirla al reves: \n");
frasereves();
printf("\n\nDeseas introducir otra frase?[S/N] \n");
scanf("%c",&eleccion);
if (eleccion == 'S')
{
continuar = 1;
}
else if (eleccion == 'N')
{
continuar = 0;
}
else
{
printf("\nERROR, el caracter introducido no es un caracter valido\n");
continuar = 0;
}
}
while (continuar == 1);
{
printf("\nADIOS! Ten un buen dia...\n");
scanf("%i",&pausa);
}
return 0;
}

//Funcion Recursiva
void frasereves()
{
char nombre;
if((nombre = getchar()) != intro)
{
frasereves();
printf("%c",nombre);
}

else aux = 1;
return;
}

El programa es funcional, pero tiene un pequeño defecto, que la función que cumpliá el famoso "toupper" no se hace, ya que lo tuve que eliminar (mira que traté de incluirlo de varias formas).

Creo que es el compilador o espero que sea un error de tecleo, pero en sí ¿Hay alguna forma de arreglar estos errores?

Salu2

PD. He tratado de compilarlo usando "Copy&Paste" pero me sigue dando error en el "toupper".

Imagen de pspgorrister

Pero no eliminies el toupper,

Pero no eliminies el toupper, esa función hace falta, tan sólo pon el header que la contiene es decir añade:

#include <ctype.h>

 

Un saludo.

 

PD: Para el que el no lo sepa, si no se pone el toupper() y se pulsa 's' (minúscula) el programa fallará.


LuaDiE: Crea en Lua sin teclear código. Compatible HM7, HMv2, LuaPlayer, LuaDEV y PGE.

Imagen de P22

Vaya...

En mi libro de C pone que las funciones toupper y tolouer(o como sea) Vienen incluidas en la biblioteca standard stdio.h

Saludos

PD: Ya lo agrego


¡Iníciate en Linux fácilmente! Sólo entra aquí y comprueba que distribución se adapta mejor a tí.

Mi review: iPod Touch 4G

Imagen de Robione22

Creo que así lo es.

Según me funcionó en C la función toupper sí viene incluida en stdio.h, a lo que se refiere pspgorrister, es a mi "port" a C++, ahora mismo lo agrego yo XD.

Salu2

Imagen de recoco

Código

Código escrito en C no en C++, por lo tanto el proyecto que elijas en Dev C++ debe de ser en C.

Saludos

Imagen de Robione22

Oops jejeje :$

Ese pequeño detalle, nunca lo noté (vaya torpe xD) ahora lo he seleccionado en C y voilá (o como se escriba) funcionó.

Gracias recoco.

Imagen de recoco

De nada

De nada, esos errores suelen ocurrir XD.

Saludos

Imagen de P22

Como...

A uno que yo me sé xD

Imagen de recoco

Ya

Ya sé quien... uhmn nose ahora no me recuerdo XD.

Imagen de moikop

:-O

Muy buen tuto P22, muy bien explicado =P

Un saludo.

Imagen de d.m.n.

Q tal, re analizando tu

Q tal, re analizando tu código vi toupper y por lo que encontré lo que hace es cambiar lo que haya en un char a MAYUS, o lo que es lo mismo, restarle 32 a cada caracter pero no hace eso, o entendí mal la función de toupper y también no faltaria incluir la libreria donde se encuentra toupper?.

También otra cosa, para que sirve la variable int pausa ?

Gracias. Risa

Imagen de pspgorrister

¿Qué quieres decir con que no

¿Qué quieres decir con que no hace eso?. La comparación que hace en el código está bien porque toupper devuelve el entero del carácter, que se puede comparar con 'S' sin problemas. Ojo devuelve el carácter en mayúsculas, no lo cambia, porque el char no se pasa como puntero.

Sobre lo de pausa, pues realmente no hace nada, supongo que lo habrá puesto para que no se le cierre la ventana o restos de un codigo borrado.


LuaDiE: Crea en Lua sin teclear código. Compatible HM7, HMv2, LuaPlayer, LuaDEV y PGE.

Imagen de P22

La variable pausa la puse

La variable pausa la puse porque si no la pones, el siguiente scanf se salta, es decir, que esta como para corregir, algo auxiliar, no hace falta ni que la miréis.

Saludos


¡Iníciate en Linux fácilmente! Sólo entra aquí y comprueba que distribución se adapta mejor a tí.

Mi review: iPod Touch 4G

Imagen de d.m.n.

Je, gracias, ya

Je, gracias, ya entendí.

Saludos.

Imagen de d.m.n.

Que paciencia, lo has

Que paciencia, lo has explicado muy bien. Aunque a mi se me da programar no tengo la paciencia para hacer un tuto :/

Gracias P22.

Imagen de P22

Si esto es paciencia, espera

Si esto es paciencia, espera al próximo :p

Imagen de pspgorrister

Bien

Siempre es agradable ver gente que se preocupa en dar conocimientos sobre técnicas de programación. Te felicito.

 

Por cierto, esto me recuerda la frase que tenía yo antes como firma:

"Para entender la recursividad, primero hay que entender la recursividad". Guiño

 

Un saludo.


LuaDiE: Crea en Lua sin teclear código. Compatible HM7, HMv2, LuaPlayer, LuaDEV y PGE.

Imagen de P22

Y que casualmente

Fue como me interese por ella :p

Ahora estoy terminando un macrotutorial que llevo haciendo como un mes, como estoy empezando en C, me he decidido a continuar los tutoriales de tanos.

Saludos


¡Iníciate en Linux fácilmente! Sólo entra aquí y comprueba que distribución se adapta mejor a tí.

Mi review: iPod Touch 4G

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.