在C++中,递归实现高效运算的关键在于减少重复计算和优化递归调用。以下是一些建议:
#include <iostream>
#include <vector>
#include <unordered_map>
int fibonacci(int n, std::unordered_map<int, int>& memo) {
if (n <= 1) {
return n;
}
if (memo.find(n) != memo.end()) {
return memo[n];
}
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}
int main() {
std::unordered_map<int, int> memo;
int n = 10;
std::cout << "Fibonacci("<< n << ") = " << fibonacci(n, memo) << std::endl;
return 0;
}
#include <iostream>
#include <vector>
int fibonacci(int n) {
if (n <= 1) {
return n;
}
std::vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
int main() {
int n = 10;
std::cout << "Fibonacci("<< n << ") = " << fibonacci(n) << std::endl;
return 0;
}
#include <iostream>
int fibonacci_tail(int n, int a = 0, int b = 1) {
if (n == 0) {
return a;
}
return fibonacci_tail(n - 1, b, a + b);
}
int main() {
int n = 10;
std::cout << "Fibonacci("<< n << ") = " << fibonacci_tail(n) << std::endl;
return 0;
}
总之,要实现高效的C++函数递归,可以使用备忘录、自底向上的动态规划和尾递归等技术来减少重复计算和优化递归调用。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
推荐阅读:c++递归函数能高效吗