2

He depurado una función que hice llamada: contar, porque estoy tratando de dominar la recursividad, pero resulta que, cuando la depuré en Dev-C++, el Call Stack se vaciaba desde que se retornaba, eso me dejó confundido... No sé como funciona, y además porque retorna 1.

Aquí el código de la función, para que me aclaren mis dudas:

int prueba(int n){
    if(n == 0){
        return 1;
    }else{
        n + prueba(n-1);
    }
}

Lo que quiero decir, es que me expliquen porque esa función funciona de esa manera y además que es lo que hace.

9
  • Esa función es incorrecta. El else no continene un return, y el comportamiento de eso es indefinido. Seguro que tuviste al menos un warning del compilador con ella.
    – Trauma
    Commented el 1 oct. 2020 a las 18:36
  • No, no tuve un warning, y sé que esa función no es correcta. Pero de todas formas solo quiero saber porque funciona de esa manera y que es lo que hace. Commented el 1 oct. 2020 a las 18:37
  • Pues te recomiendo que cambies de compilador warning: control reaches end of non-void function :-) No funciona de ninguna manera porque incurre en comportamiento indefinido. Y dudo mucho que puedas extraer conclusiones de un comportamiento que, por definición, es indefinido. Muestra un código sin problemas y entonces si podrás sacar conclusiones.
    – Trauma
    Commented el 1 oct. 2020 a las 18:42
  • Probe el código. Como C, no genera warnings. Como C++ si genera warning. En ambos casos ejecuta y retorna '1' tal como dice Black Ninja.
    – Candid Moe
    Commented el 1 oct. 2020 a las 18:43
  • Ok, gracias entonces. Commented el 1 oct. 2020 a las 18:45

2 respuestas 2

4

El comportamiento es indefinido "por definición" (valga la contradicción). Es decir, el estándar C no especifica qué debe retornar una función en la que te has olvidado de poner un return.

Sin embargo en la práctica casi todos los compiladores usan el convenio de usar el valor de un cierto registro como "recipiente" para el valor retornado. En las arquitecturas intel el registro en cuestión suele ser EAX.

En ensamblador la instrucción RET no tiene forma de especificar qué valor retornar, simplemente significa "retorna de la función" o dicho de otro modo "vuelve al punto desde el que fuiste llamada". Los compiladores C antes de ese RET ponen instrucciones que dejan en un registro (típicamente EAX como he dicho) el valor que se pretende retornar. El punto desde el que la función fue llamada recupera el valor que hay en EAX al que considera el valor retornado por la función.

Es decir, en una especie de pseudo ensamblador la cosa sería así desde el programa que llama:

meter parámetros en la pila
hacer CALL a la función
tomar lo que hay en EAX y usarlo como valor retornado

A su vez dentro de la función, en el punto de retorno, habrá algo como:

mover a EAX el valor a retornar
RET

Si olvidas retornar algo, faltará la línea que mueve a EAX el valor apropiado, y simplemente habrá un RET al final de la función.

Dicho de otro modo, el valor retornado será lo que sea que EAX contenga en ese momento. Por tanto, de forma general, será un valor impredecible porque la función pudo estar usando EAX para cualquier cosa.

Sin embargo en este caso...

En este caso ocurre que en el else hay una llamada recursiva a prueba(), por lo que se va entrando una y otra vez en esa función hasta alcanzar el caso n=0 y en ese caso sí que hay un return 1 de modo que en ese momento se hace:

MOV EAX, 1
RET

y ya que el punto al que se retorna es el final de la función, y olvidaste retornar otra cosa, desde allí simplemente habrá un RET, pero EAX todavía contiene 1. Así, todas las llamadas recursivas que habías hecho se van "deshaciendo" una tras otra a base de RET por alcanzarse el final de la función, y cuando el último RET haya sido ejecutado se volverá al programa principal y EAX todavía contiene 1, por lo que ese es el valor que se considera retornado por la función.

El código ensamblador generado por gcc para ese código es el siguiente:

prueba:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     DWORD PTR [rbp-4], edi
        cmp     DWORD PTR [rbp-4], 0
        jne     .L2
        mov     eax, 1
        jmp     .L1
.L2:
        mov     eax, DWORD PTR [rbp-4]
        sub     eax, 1
        mov     edi, eax
        call    prueba
.L1:
        leave
        ret

Se observa que tras la llamada recursiva call prueba, lo que sigue es un simple ret (leave es para restaurar ciertos registros que apuntan a la pila, pero no afectan a EAX). Por eso cuando la llamada recursiva termine, la función también termina.

Es decir, la ejecución "desenrollada" de las instrucciones que van pasando por la CPU una vez se llega al return 1, serían:

MOV EAX, 1
JMP .L1
LEAVE
RET
LEAVE
RET
LEAVE
RET
LEAVE
RET
...

hasta deshacer todos los niveles de anidamiento recursivo. Y ya que EAX no cambia de valor en esa secuencia, el valor final retornado es 1 (casualmente en este caso, indefinido de forma general).

3
  • Ya edité la pregunta, como estaba antes. La edité porque me dijieron que era un comportamiento indefinido. Casi no entiendo la explicación porque no sé ensamblador. Commented el 1 oct. 2020 a las 19:15
  • Ok. Pero aún tras editarla seguía siendo un comportamiento indefinido. La razón del comportamiento indefinido era que la función podía entrar por una rama (else) que no contenía ningún return explícito y por tanto no se sabe qué podría retornar en ese caso. Tras tu edición seguía siendo igual de indefinida, pero mucho más complicado de explicar qué ocurría.
    – abulafia
    Commented el 1 oct. 2020 a las 19:17
  • Mm ok, entiendo. Commented el 1 oct. 2020 a las 19:21
0

Es muy secillo lo que ocurre. Al llamar a la funcion la primera vez, con n=1 se va directamente al else, donde llama con el argumento n-1 , es decir, directamente 0, con lo que ejecuta return(1);

No os calenteis más.

5
  • Sigo sin entender... Commented el 1 oct. 2020 a las 19:49
  • 1
    ¿Y si lamas con argument n=15 por ejemplo? La pregunta del OP es por qué en ese caso, al depurar, va entrando sucesivamente en las llamadas recursivas hasta llegar al caso n=0 y entonces, en el return 1, aparentemente sale "de golpe" de las 15 llamadas y obtiene 1 como resultado final.
    – abulafia
    Commented el 1 oct. 2020 a las 19:59
  • Con cada llamada tras el else, hace n-1, simple. Llega un momento en que n = 0. Es decir... cada nueva llamada tras el else se hace con n acercandose a 0. Commented el 1 oct. 2020 a las 20:25
  • Y como dijo alguien por ahi, el 1 de return(1); se arrastra hasta la terminacion de la pila de llamadas. Lo increible no es que fuuncione a pesar de tener un claro error de indefinicion, funciona por error mas bien, pero lo increible es que no lo veais. Commented el 1 oct. 2020 a las 20:30
  • Y no deberiais caer en el error de mirar el ensamblador pues el codigo generado es de intel en este caso, pero bien podria generarse para otra maquina. A no ser que esteis programando microcontroladores o algo así, y aun en ese caso si se elige C es por abstraer y por tanto si se esta aprendiendo C debe centrarse en él. Commented el 1 oct. 2020 a las 20:34

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.