c++ - recursión - Dado que b siempre es distinto de cero, ¿por qué `b?--b:++ b` funciona, pero `--b` no?

recursion java

Question

Estaba tratando de multiplicar dos enteros usando la recursión, y escribí este código, accidentalmente:

//the original version
int multiply(int a, int b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, b ? --b : ++b ); //accident
}

Dije, escribí esto accidentalmente, porque tenía la intención de escribir:

b > 0 ? --b : ++b b > 0 ? --b : ++b lugar de b ? --b : ++b b ? --b : ++b

Me doy cuenta de que lo que pretendía escribir no funcionaría . Pero lo que me sorprende es que lo que no pretendía escribir funciona .

Ahora, observo que b ?--b : ++b es básicamente equivalente a --b porque se garantiza que b en else-block es distinto de cero. Así que modifiqué el código anterior, reemplazando b?--b:++b con --b , como se muestra a continuación:

//the modified version
int multiply(int a, int b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, --b); //modification here
}

Desde la versión original de woks, esperaba que la versión modificada funcionara también. Pero de nuevo, para mi sorpresa, ¡ no funciona!

• ¿Qué hay de malo en la versión modificada?
• ¿No es equivalente a la versión original?
• ¿Es --b no equivalente a b ?--b : ++b IF b es distinto de cero? Si es equivalente, entonces ¿por qué el primer código funciona pero el segundo no?

Nota: aquí, por "trabajo", quiero decir que da el resultado correcto. Es decir, da la multiplicación de los enteros pasados ​​a la función.

Answer 1

Pero lo que me sorprende es que lo que no pretendía escribir funciona.

Aparentemente, lo que está sucediendo es que en el nivel de optimización 2 en g ++ el compilador ve correctamente que si b es positivo, su código es equivalente a a * b. Aparentemente, también ve que si b es negativo, su código invoca un comportamiento indefinido. El compilador optimiza ese comportamiento indefinido al generalizar a a * b en todos los casos. Aquí está el ensamblador de g ++ -O2 (i686-apple-darwin10-g ++ - 4.2.1):

.globl __Z8multiplyii
__Z8multiplyii:
LFB1477:
   pushq %rbp
LCFI0:
   movq  %rsp, %rbp
LCFI1:
   xorl  %eax, %eax
   testl %esi, %esi
   je L5
   movl  %esi, %eax
   imull %edi, %eax
L5:
   leave
   ret 

No confío en los optimizadores. En la OMI, la respuesta del compilador al reconocer el comportamiento indefinido debería ser una falla de compilación en lugar de optimizar el comportamiento indefinido.

Editar

En lugar de agregar otra respuesta como otra respuesta, agregaré otra respuesta como edición.

Pregunte a cualquier físico el valor de la suma infinita 1 + 2 + 3 + ... y le dirán que es -1/12. (Por ejemplo, consulte http://math.ucr.edu/home/baez/qg-winter2004/zeta.pdf ). Esto va por el camino largo funciona por un truco similar de dos complementa la aritmética. Una solución que no implica ir por el camino largo para los números negativos:

int multiply (int a, int b) {
   if (b == 0) {
      return 0;
   }
   else if (b < 0) {
      return -multiply (a, -b);
   }
   else {
      return a + multiply(a, b-1);
   }
}

Incluso en altos niveles de optimización, mi compilador ya no es lo suficientemente inteligente como para reconocer lo anterior como una multiplicación. Dividir lo anterior en dos funciones y el compilador una vez más reconoce que lo que se está haciendo es la multiplicación de enteros:

int multiplyu(int a, unsigned int b) {
   return (b == 0) ? 0 : a + multiplyu(a, b-1);
}

int multiply(int a, int b) {
   return (b < 0) ? -multiplyu (a, -b) : multiplyu (a, b); 
}

Answer 2

Ambas formas de multiply bloquean en Visual Studio con un desbordamiento de pila, cuando b es negativo.

Entonces, la respuesta es, ninguna forma es correcta. Probablemente, lo que está sucediendo en gcc es que, debido a algunas peculiaridades (¡no a un error!) El compilador está optimizando la recursión de cola en el primer ejemplo, pero no en el segundo.

Como nota al margen, incluso si lo cambia a b > 0 ? --b : ++b b > 0 ? --b : ++b , todavía no estás multiplicando por el signo de b (por ejemplo, multiply(-1, -1) == -1 )

Answer 3

De hecho, no tiene nada que ver con --b, sino con su algoritmo.

Si b <0, ¿qué esperas? Realizará un bucle indefinido y terminará con un desbordamiento de pila.

Esta es la razón por la que tiene el resultado correcto al principio multiplicar (12, 7), pero luego su programa falla cuando se llama multiplicar (12, -7).

Answer 4

Debido a la forma en que funcionan los números complementarios de 2, su código es "correcto" para los valores positivos y negativos para b. Es solo que para las b negativas, cualquier versión recursiva necesita una gran pila para funcionar. Así que cada vez que el compilador emite una versión no recursiva, tiene un código de trabajo. Así que se reduce a: ¿qué regla utiliza mi complaciente para determinar cuándo emitir código no recursivo? Eso solo depende de cómo fue escrito el compilador.

Answer 5

La salida del código de abajo debería dar una pista muy fuerte;)

#include <iostream>

using namespace std;

int multiply(int a, int b)
{
  cout << "a = " << a << "/tb = " << b << std::endl;
  if ( !b )
     return 0;
  else
     return a + multiply(a, b ? --b : ++b );
}

int main() {
        cout << multiply(12, 7) << endl;
        cout << multiply(12, -7) << endl;
        cout << multiply(-12, -7) << endl;
        cout << multiply(-12, 7) << endl;
        return 0;
}

A mí me parece que está recibiendo la respuesta yendo por el camino largo.

Edit: En respuesta al comentario de Nawaz a continuación, el primer método funciona debido a los caprichos de la aritmética de enteros con signo de complemento de dos. Como dije, toma el camino largo. Está habilitado, como otros lo han señalado debido a alguna optimización del compilador u otra. Puede ver esto en el siguiente código para la entrada de prueba proporcionada anteriormente:

int mul2(int a, int b)
{
    int rv = 0;
    while (b--) rv += a;
    return rv;
}

De hecho, debería funcionar para cualquier par de enteros, pero tomará algún tiempo para ejecutarse en algún caso (pero espero que no haya interés en la eficiencia en ningún caso).

El segundo caso no funciona porque su condicional b > 0 ? --b : ++b b > 0 ? --b : ++b convierte esencialmente b en abs(b) . Es decir, solo agrega 7 veces en su caso de prueba aunque b = -7. Si quisiera que se comportara de la manera que creo que quería que se comportara, tendría que hacer algo como:

int multiply(int a, int b)
{
  if ( !b )
     return 0;
  else if (b < 0)
     return -a + multiply(-a, -b-1);
  else
     return a + multiply(a, --b);
}

Edición 2: intente esto en su lugar:

short multiply(short a, short b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, b ? --b : ++b );
}

y

short multiply(short a, short b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, --b);
}

Ambos compilan, ejecutan y devuelven el mismo resultado (correcto) con o sin optimización. Como han señalado otros, la causa de la diferencia de tiempo de ejecución que está viendo solo se puede atribuir a la forma en que el compilador está optimizando su código. Deberá analizar el código de ensamblaje de los dos métodos para determinar la causa raíz de las discrepancias de tiempo.

Answer 6

No funciona No sé qué ideone está fumando, ese código va a desbordar la pila.

EDITAR

Lo probé en gcc 4.6.0 - segfault (debido al desbordamiento de pila). Sin embargo, si habilita -O2 optimizaciones -O2 , entonces efectivamente "funciona". En conclusión: funciona por casualidad, dependiendo de lo que el compilador haga entre bastidores.

g++ -g -Wall -o f f.cpp # 
g++ -O2 -g -Wall -o f f.cpp # "works"

Answer 7

TL; versión DR: ¿ La razón b? --b: ++b b? --b: ++b imprime un resultado y --b falla con SIGXCPU es que ideone establece un límite de tiempo en el código enviado. Una versión se optimiza mejor y se completa en el tiempo permitido. La otra versión da exactamente la misma respuesta, pero no verá eso con ideone porque se ejecuta muy lentamente y se interrumpe por el límite de tiempo.

En cuanto a por qué no se produce el desbordamiento de pila, supongo que en un caso el compilador debe transformar la recursión en iteración (esto no es una llamada de cola, pero es trivialmente transformable).

El resultado de la transformación sería algo así como http://ideone.com/AeBYI que de hecho da el resultado correcto. Con ajustes de optimización más altos, el compilador podría calcular los resultados en tiempo de compilación y almacenar constantes en el código resultante.