Recursion without recursive call?

Found this on /prog/. I actually GDB'd it, and yes, it was truly a recursion. But how did it happen?

// This works on 32-bit x86 Linux with gcc as long as you don't enable optimization.

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

static void factorial(int in, int *out)
{
  *(&in-1)-=5-5*(1/in);
  *out*=in--;
}

int main(int argc, char **argv) 
{
  int result=1;
  int number=0;

  if (ar开发者_Go百科gc!=2) 
    exit(1);

  number=atoi(argv[1]);
  if (number<1)
    exit(2);

  factorial(number, &result);
  printf("%d! = %d\n", number, result);
  return 0;
}


$ ./factorial 3
3! = 6

$ ./factorial 5
5! = 120

Sweet. ;)

This is extremely non-portable code that works only on x86. What it's doing is changing the return address on the stack so that if in>1, the function returns not to the instruction following the call instruction, but to the call instruction itself. A call instruction on x86 is five bytes (one opcode plus the 4-byte address of the call destination), so five needs to be subtracted from the return address.

This

*(&in-1)-=5-5*(1/in);

is just an obfuscated way of saying

if(in>1)
    *(&in-1)-=5;

And &in-1 is where the return address lives on the stack.

It's corrupting return addresses on the stack to cause the recursion to happen.

*(&in-1)-=5-5*(1/in);

&in-1 is probably the pushed return address. the rest is just unpleasant magic.

As said before *(&in-1) is the return address, 5 (I guess) is the size of the function (in words?) and it substract both to get the address where the function begins.

EDIT: Since I think the change to the return address is permanent I don't understand why 5 is subtracted while in > 1;

EDIT2: See the comments

The assembler return instruction only jumps to the address that is on the top of the stack.

Due to the calling convention the parameters are pushed to the stack and removed from it by the caller. Since there is only one real call there is no recursion, the parameters and the return address (pointer) are shared among the iterations.

It is more like a loop than a recursive function.