我正在設計一個遞回演算法，以創建一個計算兩個正整數乘積的函式。我的偽代碼有問題。基本思想：
- 函式定義必須是“int Product(int a, int b)”，
- 執行遞回呼叫，直到達到基本情況，
- 每一步都將“a”添加到區域變數“result”。
迭代方法有效，并且很容易實作（暫時忽略正整數的限制，所以只需考慮它們是整數。我稍后會添加該條件）：
int Product(int a, int b) {
int result = 0;
for (int i = 0; i < b; i ) {
result = a;
} return result;
}
int main(void) {
int c = Product(3, 2); // 6
return 0;
}
現在，我讀到如果我想從遞回演算法中的迭代演算法轉換，我所要做的就是以另一種方式重寫 for 回圈：
- for 回圈的檢查條件（即 i < b）是基本情況，
- for 回圈體（即結果 = a）是遞回步驟。
但問題是我不知道如何在不使用回圈的情況下撰寫遞回演算法（因為如果我使用回圈，我就沒有使用遞回方法）。而且沒有回圈，創建區域變數“i”作為計數器是沒有意義的，因為我不能使用 goto 命令向后跳轉。
uj5u.com熱心網友回復：
一個for回圈模式為：
func() {
for (int i=0; i<N; i ) {
body
}
}
可以重寫為以下遞回模式：
for_func(int i) {
if (i<N) { body; for_func(i 1); }
return;
}
然后你可以重寫：
int Product(int a, int b) {
int result = 0;
for (int i = 0; i < b; i ) {
result = a;
}
return result;
}
作為：
int rec_Product(int result, int i, int a, int b) {
if (i<b) {
return Product(result a,i 1,a,b);
} else {
return result;
}
}
int Product(int a, int b) {
return rec_Product(0,0,a,b);
}
uj5u.com熱心網友回復：
由于函式中的 for 回圈，您在這里所做的不是遞回函式。您需要按如下方式實作它：
#include <stdio.h>
int product(int prod, int amount) {
if (amount == 0)
return 0;
return prod product(prod, amount - 1);
}
int main() {
int c = product(2, 3);
return 0;
}
uj5u.com熱心網友回復：
您所描述的是將迭代函式轉換為遞回函式的一般方法。
然而，遞回函式可以有自己的特殊性。
例如，希望減少遞回呼叫的數量以避免堆疊溢位。
引入中間變數可能是多余的。
至于你的函式，它的引數應該是無符號整數型別unsigned int。否則，該函式可能具有未定義的行為。
函式的回傳型別應該是unsigned long long避免大數產生的溢位。例如，如果您將在第一個引數等于INT_MAX且第二個引數等于時呼叫您的函式，2那么您的函式將回傳無效結果。
考慮到所有這些，可以通過以下方式定義函式
#include <stdio.h>
unsigned long long int product( unsigned int a, unsigned int b )
{
return b == 0 ? 0 : a product( a, ( b - 1 ) / 2 ) product( a, b - 1 - ( b - 1 ) / 2 );
}
int main( void )
{
unsigned int a = 2;
for (unsigned int b = 0; b < 11; b )
{
printf( "%llu ", product( a, b ) );
}
putchar( '\n' );
}
程式輸出為
0 2 4 6 8 10 12 14 16 18 20
該函式的思想基于以下關系：如果 b 等于 n1 n2，則 a * b 等于 a * ( n1 n2 )，即 a *n1 a * n2。也就是說，您可以減少函式遞回呼叫的級別數。
函式的回傳陳述句也可以寫成
return b == 0 ? 0 : ( --b, a product( a, b / 2 ) product( a, b - b / 2 ) );
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/444589.html
上一篇：鏈接串列可以只是一個類嗎？