x86 汇编中的递归 Ackermann-Peter 函数 (NASM)

Question

我正在尝试在 x86 NASM-Assembly 中实现递归 Ackermann-Peter-Function。该函数定义如下：

*a(0;m) = m + 1

*a(n + 1; 0) = a(n; 1)

*a(n + 1;m + 1)) = a(n ; a(n + 1;m))

我的问题是我什至无法想象如何正确开始。到目前为止，我只在汇编中递归地实现了“x 的幂”函数。

这是我到目前为止所拥有的： http://pastebin.com/rsWALyCq （德语提示只要求 n 和 m）

我感谢每一位我可以通过这个获得帮助。

--

所以我现在将推送/弹出语句设为对称，但仍然出现分段错误。我尝试调试整个事情并在第一个案例中放置了一条调试消息。我编译了该程序并使用 n=0 和 m=0 进行了尝试，但他没有打印调试消息，因此他甚至没有输入第一种情况。我似乎无法找出他为什么不这样做。

这是我目前的尝试： http://pastebin.com/D4jg7JGV

Answer 1

解决方案：

好吧，我发现了问题：

我没有正确管理 ebp 和 esp。因此，我现在在每个函数调用中都使用了 ENTER 和 LEAVE 宏，现在整个事情都可以正常工作了。
这是解决方案。感谢您的宝贵时间：

asm_main:
    ENTER 0,0               ;setup Routine
    PUSHA
    MOV eax, prompt1        ;ask for n

完整代码：
http://pastebin.com/ZpPucpcs

Answer 2

如果您可以递归地执行此操作（伴随所有随之而来的堆栈帧增长），那么这相当简单。基本思想，在子程序的代码中：

ACKERMANN
Get n and m off the stack or from registers
Compare n to zero.
If it is equal, jump to FIRSTCASE
Compare m to zero
If it is equal, jump to SECONDCASE
put n + 1 into the first argument slot
put m into the second argument slot
call ACKERMANN
put n into the first argument slot
put the return of previous call into second argument slot
call ACKERMANN
put the return of the previous call into the return register/stack slot
return

FIRSTCASE
put m+1 in the return register/stack slot
return

SECONDCASE
Put n into the first argument slot
put 1 into the second argument slot
call ACKERMANN
put the return of previous call into return register/stack slot
return