考試僞遞歸函數

-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

考試僞遞歸函數

回答

相關問題