考试伪递归函数

-4

看伪代码的这个例子：

algorithm A(a, b) { 
    // precond: a & b are type of Int 
    // postcond: what does this function return? 
    if (a == b) 
     return(0) 
    else if (a < b) 
     return (-A(b, a)) 
    else 
     return (A(a-1, b-1)); 
}

给出的答案是：

一）AB
B） a + b
c）max（a，b）
d）将无限循环

我个人认为这是d），但我只是想确定。

来源

2014-06-24 Marcin Bauer

在您的计算机上尝试它。 –

是的，我把它写在Flash（AS3.0）中，当我设置（1,2）或（2,1）时，我的程序崩溃了，但我不确定它是否只是Flashs故障。对不起，如果这个例子看起来很愚蠢。我的女朋友在考试时接受了它，而且大多数人都认为这个问题存在一个错误。 –

该函数在a==b终止;所以为了表明它不是终止，你可以证明一个&b不会与连续的调用靠得更近 - 在这种情况下，这很容易。

（以上不考虑溢出。另外，（d）不能是正确的，因为它不环在所有。）

来源

2014-06-24 16:23:42

+1提到没有循环:)答案d）应该是这样的：它导致无限递归 – GameDroids

-1

该函数将返回的唯一值是0 。那就是当一个== b。但是，对于所有（a，b），0 = a - b，所以a == b。所以我认为正确的答案是a）。

来源

2014-06-24 16:26:57

只要A和B不相等，

如果a小于b，下一个函数调用将使A> B。（例如，调用A（3,4）将返回-A（4,3））

随后，函数调用将导致无限递归，因为它会一直返回A（a-1，b-1 ）没有终止。（例如，呼叫A（4,3）将返回A（3,2），其将返回A（2,1）等等）

来源

2014-06-24 16:27:11

考试伪递归函数

回答

相关问题