我需要將此遞回函式轉換為尾遞回函式，但我得到錯誤的輸出可以幫助我解決這個問題。
下面是函式定義：
f(n) = 3f(n ? 1) - f(n ? 2) n, 具有初始條件f(0) = 1和f(1) = 2。
#include <iostream>
using namespace std;
int headRecursion(int n) {
if(n == 0) {
return 1;
}
if (n == 1) {
return 2;
}
return 3 * headRecursion(n - 1) - headRecursion(n - 2) n;
}
int main(){
cout << endl << headRecursion(3);
return 0;
}
uj5u.com熱心網友回復：
這是一個很有趣的問題。我們可以從如何實作為回圈開始：
int minus2 = 1;
int minus1 = 2;
if (n == 0) return minus2;
if (n == 1) return minus1;
for( int i = 2; i <= n; i )
{
int next = minus1 * 3 - minus2 i;
minus2 = minus1;
minus1 = next;
}
return minus1;
要點是我們需要向上計數。為了使這個尾部遞回，我們需要傳入我們的累加器（除了炫耀之外沒有理由這樣做，但這不會增加可讀性或效率）
int tailRecursive(int minus2, int minus1, int step, int n)
{
if (step == n) return minus1;
return tailRecursive(minus1, minus1*3 - minus2 step 1, step 1, n);
}
您可以使用中間件來設定它并處理 n==0 情況。
int calcIt(int n) {
if (n == 0) return 1;
// step must start with 1, since we handled 0 above
return tailRecursive(1, 2, 1, n);
}
uj5u.com熱心網友回復：
沿著這些路線的東西：
std::pair<int, int> next_result(std::pair<int, int> prev_result, int n) {
return {3*prev_result.first - prev_result.second n, prev_result.first};
}
std::pair<int, int> tailRecursion(int n) {
if (n == 0) {
return {1, 0};
}
if (n == 1) {
return {2, 1};
}
return next_result(tailRecursion(n-1), n);
}
int compute(int n) {
return tailRecursion(n).first;
}
int main(){
std::cout << compute(3) << std::endl;
}
演示
關鍵是您需要一個函式來計算{f(n), f(n-1)}給定先前計算的對{f(n-1), f(n-2)}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/344881.html
上一篇：理解字串置換遞回案例之間的區別