¿Qué está pasando realmente en este código?

6 minutos de lectura

¿Que esta pasando realmente en este codigo
fantasma

Tengo un código que incluye una función recursiva. He perdido mucho tiempo en la recursividad, pero todavía no pude entenderlo realmente:

#include<stdio.h>
void count(int);

int main()
{
    int x=10,z;
    count(x);
}

void count(int m)
{
    if(m>0)
        count(m-1);
    printf("%d",m);
}

cuando la 1ra vez count se llama con argumento como 10. cumple la condición y luego aquí comienza la parte recursiva. ¿Qué sucede realmente cuando una función se llama a sí misma? no lo entiendo Por favor explique con referencia a las pilas.

  • por favor explique con referencia a las pilas

    – Fantasma Iscuming

    4 de septiembre de 2012 a las 14:21

  • Simplemente “comienza” de nuevo, con el nuevo parámetro. Es como una llamada a cualquier otra función. Intente anotar los pasos de ejecución en un papel para ver qué sucede. Con número menor, por ejemplo con 3.

    – Kiril Kírov

    4 de septiembre de 2012 a las 14:21

  • @Let_me_be: ¿por qué realizó cambios de estilo en el código de la pregunta? (También pasa a ocultar un comportamiento indefinido)

    – Flexografía

    6 sep 2012 a las 12:33


1647729669 456 ¿Que esta pasando realmente en este codigo
md5

Tiempo m es mayor que 0, llamamos count. Aquí hay una representación de las llamadas de la pila:

 count (m = 10)  
   count (m = 9)  
     count (m = 8)  
       count (m = 7)  
         count (m = 6)    
           count (m = 5)     
             count (m = 4)     
               count (m = 3)     
                 count (m = 2)     
                   count (m = 1)
                     count (m = 0)
                     printf 0
                   printf 1
                 printf 2
               printf 3
             printf 4
           printf 5
         printf 6
       printf 7
     printf 8
   printf 9
 printf 10

1647729670 719 ¿Que esta pasando realmente en este codigo
00jt

la próxima vez que se llama a sí mismo tiene un valor menor

count(int m)
{
 if(m>0)
 count(m-1); // now it is calling the method "count" again, except m is one less
 printf("%d",m);
}

Así que primero llamará a contar con 10, luego lo llamará con 9, luego 8, luego 7… todo el camino hasta que esta afirmación if no sea verdadera:

if(m>0)

Lo que podría confundirlo es que la declaración if solo se aplica a la siguiente línea (printf no es parte de la declaración if)

así que tienes:

count(int m)
    {
     if(m>0)
     {
         count(m-1); // now it is calling the method "count" again, except m is one less
     }
     printf("%d",m);
    }

Entonces, las llamadas recursivas se detendrán una vez que m no sea > 0, y luego llamará a printf.

Después de llamar a printf para cuando m es 0, luego regresará de esa llamada de ‘recuento’ (Volver a donde m era igual a 1), y luego llamará a printf cuando m sea 1, y luego cuando m sea 2 , …..

Entonces la salida debería ser:

"0 1 2 3 4 5 6 7 8 9 10"

EDITAR: En términos de una pila:

Esto es lo que está haciendo la pila:

count(10) // push count(10)

->

count(9) // push count(9)
count (10)

->

->

count(0) // push count(0)
count(1)
count(2)
count(3)
count(4)
count(5)
count(6)
count(7)
count(8)
count(9)
count(10)

-> (y luego comienza a imprimir y sacar el método de la pila)

// pop count(0), and printf(0)
count(1)
count(2)
count(3)
count(4)
count(5)
count(6)
count(7)
count(8)
count(9)
count(10)

->

// pop count(1), and printf(1)
count(2)
count(3)
count(4)
count(5)
count(6)
count(7)
count(8)
count(9)
count(10)

->

->

// pop count(9), and printf(9)
count(10)

->

// pop count(10), and printf(10)

  • ahora que lo veo es una etiqueta de tarea. (y usted está preguntando acerca de las pilas). ¿Tiene un conocimiento básico de las pilas?

    – 00jt

    4 de septiembre de 2012 a las 14:27


  • Cada vez que se llama “contar”, se coloca en la pila. Una vez que se llama al último “conteo”, llama a “printf” y esa llamada de conteo se saca de la pila. Trataré de mostrar eso en mi respuesta.

    – 00jt

    4 sep 2012 a las 14:37


Cuando se llama a una función, la dirección de retorno (del siguiente código a ejecutar) se almacena en la pila junto con sus argumentos actuales. Una vez que la función finaliza, la dirección y los argumentos aparecen para que la CPU sepa dónde continuar con la ejecución del código.

Escribamos las direcciones de la función (solo para el propósito de este ejemplo)

count(int m)
{
(address = 100)  if(m>0)
(address = 101)     count(m-1); // now it is calling the method "count" again, except m is one less
(address = 102)  printf("%d",m);
}

Para m = 1:

los if es fullfield por lo que ejecutamos el código en address 101 con m = 1. address 102 y m = 1 se empujan a la pila y la función se ejecuta de nuevo desde address 100 con m = 0. Ya que m = 0 ejecutamos address 102 e imprimiendo 0 en la consola. La función termina y el último retorno. address (102) y argumento m = 1 aparecen y la línea en address 102 se ejecuta imprimiendo un 1 en pantalla.

  1. La función count se llama con un argumento entero de 10.
  2. Dado que el argumento de la función m cual es 10 es mayor que 0 la función count se llama a sí mismo con un argumento entero de m cual es 10 menos 1 que es igual 9.
  3. El paso 2 se repite con diferentes argumentos (m-1) Hasta que m no es mayor que 0 y en qué punto el programa imprime el valor de m.

La función recursiva simplemente modifica el parámetro que se le ha dado y se llama a sí misma con ese valor modificado hasta que se devuelve el resultado deseado (en este caso m no siendo mayor que 0).

Cada número se refiere al número de línea.

#include<stdio.h>
count(int);
main()
{
1int x=10,z;
2count(x);
}  
count(int m)
{
3if(m>0)
4   count(m-1);
5printf("%d",m);
}

La ejecución ocurre así (con x=3) –

número de línea|valor de x

1 3

2 3

3 3

4 2

3 2

4 1

3 1

4 0

5 0

5 1

5 2

5 3

Números impresos en la pantalla 0 1 2 3

1647729671 7 ¿Que esta pasando realmente en este codigo
usuario1443778

Si desea una respuesta más específica, debe investigar cómo funcionan los compiladores. Pero, en términos generales, el compilador creará un código de máquina para la función que incluye un preámbulo, en este código se asigna suficiente memoria en la pila (disminuyendo un puntero de pila) para que se pueda colocar una copia de las variables de funciones en la pila (podemos almacenar el estado de la función).

La función tendrá valores almacenados en registros y memoria y estos deben almacenarse en la pila para cada llamada (recursiva), de lo contrario, la nueva llamada sobrescribirá los datos valiosos. Básicamente, el código de la máquina se ve así (pseudocódigo)

//store m on the stack 
store m,stack_pntr+m_offset
//put input values in designated register
a0 = m
//allocate memory on the stack
stackPntr -= stack_size_of(count_vars)
//store return address in allocated register
//jump to the first instruction of count
.
.

Al cambiar algunos datos utilizados para el cálculo, podemos volver atrás y leer las mismas instrucciones nuevamente y obtener un resultado diferente. La abstracción de la función recursiva nos permite manipular los datos que queremos cambiar de una manera agradable de “llamada por valor” para que no los sobrescribamos sin querer.

Esto lo hace el compilador cuando almacena el estado de la función de llamada en la pila para que no tengamos que almacenarlo manualmente.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad