recursive factorial

r0nn

I'm trying to implement recursive factorial in assembly. I have two functions, caller and the function being invoked. I'm not sure what I'm doing wrong but when I try to run the code, I get a very large negative number for an answer regardless of input.

[code]
f(unsigned int input,unsigned int *output)
{
__asm{
push ebx //param2
push ecx //param1
call factorial
pop ecx //pop in reverse order
pop ebx
mov ebx, eax //copy result
ret
}

}

__declspec(naked) unsigned int
factorial(unsigned int n)
{
__asm{
push ebx
mov ebx, dword ptr [esp+8] //copy param into a register
cmp ebx, 1
jg RECURSE
mov eax, 1 //accumulator
jmp END

RECURSE:
dec ebx //n-1
push ebx
call factorial
pop ebx
inc ebx
mul ebx


END:
pop ebx
ret

}
}
[/code]

I appreciate any suggestions or comments. Thanks!

anthrax11

I think it would make much more sense to do this in either pure C or pure assembly, it gets really messy as mixed C/asm.
[code]
void
f(unsigned int input,unsigned int *output)
{
*output = factorial(input);
}

unsigned int
factorial(unsigned int n)
{
if (n > 1)
return n * factorial(n-1);

return 1;
}
[/code]


The problem with your code is the way you handle parameters.
[code]
[color=Blue]// Missing type here, I'll take a guess
__declspec(naked) unsigned int[/color]
f(unsigned int input,unsigned int *output)
{
__asm{
[color=Blue] /*
ebx, ecx, etc. are not parameters, they are registers.
In a Windows environment, ebx, esi and edi should
be saved in case you use them. The factorial function
already saves ebx, so no need to save anything here.
The parameters are stored in a memory location called the stack,
the esp register points to the top of the stack.
The first dword on the stack is the return address to
the function that calls f. The next dwords are the
parameters and that's how we know how to access them.
*/
push dword ptr[esp+4][/color] // Input parameter
call factorial

[color=Blue] /*
The factorial function does not clean up the stack
because of __declspec(naked). This means that the input
parameter is still on top of the stack, so just pop it back
into an unused register
*/
pop ecx[/color]

mov [output], eax //copy result
ret
}
}
[/code]
If you wan't to learn more about this, then search the net:
http://unixwiz.net/techtips/win32-callconv-asm.html
http://en.wikibooks.org/wiki/X86_Disassembly/Functions_and_Stack_Frames
I think stack management is one of the most complex topics to learn in assembly, but it's a really useful thing to know about.

Bret

I'm wondering why you would implement this as a recursive subroutine call, rather than as a simple loop. A loop would be faster and use less memory.

r0nn

Thanks for pointing that out, that was the mistake.

r0nn

We are required to implement this recursively and were told that we won't get credit if we didn't. But yeah I understand your point that it's much easier to just do it in a loop.