| Ver tema anterior :: Ver siguiente tema | | Autor | Mensaje |
|---|
rocklee
Registrado: 09 May 2011
Mensajes: 3
|  Publicado: 10/05/2011 6:41 am | | | Título: Invertir cadena de caracteres |
| Hola. Llevo unos meses estudiando programación en C y por primera vez me he encontrado con una función cuyo ´funcionamiento´ (disculpen la redundancia) no entiendo. Se trata de una función recursiva utilizada para invertir una cadena de caracteres e imprimir esta en pantalla. La función se llama ´reverse´ y muestro su prototipo, definición y uso en el programa siguiente:
| Código: |
#include <stdio.h>
#include <stdlib.h>
void reverse (char*);
int main(){
char sentence [80];
printf ("Entre una cadena\n");
gets(sentence);
printf ("La cadena invertida es\n");
reverse (sentence);
printf ("\n");
return 0;
}
void reverse (char* s){
if (s[0]=='\0')
return;
else{
reverse (&s[1]);
putchar (s[0]);
}
}
|
El problema que tengo es que no entiendo cómo es que la fucnicón 'reverse' logra imprimir una cadena arbitria entrada, pues el enunciado
se encuentra después de la llamada a la función
Veo que esto es un función recursiva, pero en el ´debuggeo mental´ que yo me hago, se alcanzará el enunciado de 'return;' sin nunca imprimir nada. Estoy usando como entorno el Visual Estudio 2008.
Esta es la primera vez que publico en este foro. Si mi pregunta dedería estar en otra parte, por favor avísenme.
Gracias
_________________
De la serie Naruto, mi personaje preferido es Rock Lee, porque a diferencia de otros muchos ninjas, este no nació con ninguna habilidad especial; todo lo que ha logrado, lo ha logrado con su esfuerzo propio. Mucho esfuerzo, esa es la clave. |
| | Volver arriba | |  | rir3760
Registrado: 01 Oct 2004
Mensajes: 7520
Ubicación: Mexico
| | Publicado: 10/05/2011 7:47 am | | | Título: |
| Para empezar no es el mejor ejemplo de programacion en C debido al uso de la funcion gets (mejor fgets) pero eso se puede tratar despues.
La funcion recursiva no es dificil, la clave es entender que la llamada recursiva se realiza antes del proceso.
Para explicarlo mejor considera que la cadena a procesar es "hola", esta se almacena en el array como esa secuencia de caracteres mas un '\0' (un cero) para marcar el final de esta:
| Código: | s[0] = 'h'
s[1] = 'o'
s[2] = 'l'
s[3] = 'a'
s[4] = '\0' |
La llamada a la funcion se realiza de esta forma, con la primera llamada pasando la direccion de "s[0]" que es el caracter 'h':
| Código: | 1) ¿Es 'h' igual a '\0'? NO --> llamada recursiva
2) ¿Es 'o' igual a '\0'? NO --> llamada recursiva
3) ¿Es 'l' igual a '\0'? NO --> llamada recursiva
4) ¿Es 'a' igual a '\0'? NO --> llamada recursiva
5) ¿Es '\0' igual a '\0'? SI --> fin de la funcion
6) Se imprime el caracter 'a', fin de la funcion
7) Se imprime el caracter 'l', fin de la funcion
8) Se imprime el caracter 'o', fin de la funcion
9) Se imprime el caracter 'h', fin de la funcion |
De nuevo el punto clave para entender la recursion es que las llamadas recursivas se ejecutan en secuencia sin realizar nada hasta alcanzar la condicion de escape (se localiza el caracter '\0').
Una vez alcanzado ese punto las llamadas recursivas terminan imprimiendo el caracter (con excepcion del '\0'): primero el ultimo (la 'a'), despues el penultimo (la 'l'), etc.
Espero todo esto no te haya confundido (mas).
Un saludo
_________________
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language |
| | Volver arriba | | | Pantalàimon_
Registrado: 17 Jul 2007
Mensajes: 1345
| | | Volver arriba | | | | rocklee
Registrado: 09 May 2011
Mensajes: 3
| | Publicado: 10/05/2011 11:15 am | | | Título: |
| Gracias por la ayuda tan rápida. Ya analicé lo que me dicen y me percaté del problema que tuve. Es que pensaba que una vez alcanzado el enunciado ´return;´, cuando s[0]=='\0' se abandonaba la funcion completamente, y no es asi, sino que se retorna al punto donde la funcion fue llamada, para luego imprimir el caracter al que se refiere s[0] en el momento en que se llamó a la función. Así es que se imprime el caracter 'a' por ejemplo, el último de la cadena "hola", pues al llamar a 'reverse' con el caracter nulo '\0' no se realiza ninguna acción y se continua imprimiendo el caracter 'a' que es al que se refiere s[0] cuando s[1] se refiere al nulo. Una vez hecho esto, se retorna al punto donde la funcion fue llamada con el caracter 'a', es decir, cuando s[1]=='a', imprimiendose s[0], es decir 'l'. Asi funciona hasta imprimir la cadena completa de forma invertida.
Este ejemplo me parece bastante curioso.
_________________
De la serie Naruto, mi personaje preferido es Rock Lee, porque a diferencia de otros muchos ninjas, este no nació con ninguna habilidad especial; todo lo que ha logrado, lo ha logrado con su esfuerzo propio. Mucho esfuerzo, esa es la clave. |
| | Volver arriba | | | cheroky
Registrado: 22 Sep 2005
Mensajes: 2558
Ubicación: Valladolid (España)
| | Publicado: 10/05/2011 1:09 pm | | | Título: |
| Hola.
@rocklee, lo has explicado razonablemente bien. Para verlo desde un angulo más cercano habría que conocer como funciona la pila sin entrar en detalles escabrosos.
- Cada vez que se hace la llamada recursiva se crea un nuevo marco de pila y decrece el puntero (registro) de la misma para almacenar el valor que direcciona el puntero a cadena. Visto de esta manera es similar por no decir igual que copiar los valores a un nuevo array o más bien conjunto de variables no contiguas. Tendremos entre medias almacenadas la dirección de retorno y el respaldo del puntero-base de pila.
- Ergo cuando se cumple la condición de salida se retorna (sucesivamente) al mismo punto de la llamada que se ha ido almacenando en la pila, justo antes de la llamada a putchar, es decir, este va impriendo en orden inverso los caracteres almacenados.
Te felicito por tu compresión del problema.
Hay que considerar que aunque la implementación es simple tiene un coste de memoria en el mejor de los casos M(2n), (siempre memoria local) y aunque en complejidad es O(2n), el argumento anterior y el coste de las llamadas por carácter desaconsejan rotundamente su uso.
Por otra parte la función es más legible si eliminamos los operadores de indexación.
| Código: | void reverse (const char* s)
{
if (*s == '\0')
return;
else
{
reverse (s + 1);
putchar (*s);
}
} |
·?0ƒ·
_________________
La cuestión no es si hay vida inteligente en otros planetas lejanos. La cuestión es si hay vida inteligente aquí. |
| | Volver arriba | | | | |
| No puede crear mensajes
No puede responder temas
No puede editar sus mensajes
No puede borrar sus mensajes
No puede votar en encuestas
|
|
| |
F.A.Q.
Conéctese para revisar sus mensajes