如何在某个级别停止递归函数，并在那里插入另一个函数

Question

我有两个问题：我有一个递归函数M(n)=3*M(n/2)+2*n+1和一个迭代函数T(n)=n^2

#include<stdlib.h>
#include<bits/stdc++.h> 
using namespace std; 

int M(int n) 
{ 

if (n == 1) 
return n; 
return 3*M(n/2)+2*n+1; 

} 
int T(int n) 
{  
return n^2; 

} 
int main () 
{ 

cout<< "Cost is "<< M(768)<<"n";
getchar(); 
return 0; 
} 

我想为n=768运行5个级别的递归M函数，然后插入T函数，如下所示：

M(768(=3*M(384(+O(n(

M(384(=3*M(192(+O(n(

M(192(=3*M(96(+O(n(

M(96(=3*M(48(+O(n(

M(48(=3*M(24(+O(n(

现在我希望我的程序在n=24停止，并插入$T(24)=24^2$而不是M(24)。

换句话说，我想以这种方式组合M(n(和T(n(函数。

但是我不能用这种方式安排递归代码。有人能帮我吗？我需要将M(n(转换为迭代函数来实现我的目标吗？或者我可以修复递归吗？如果是，我如何转换为迭代函数？

我的第二个问题是：

如果我运行M(n)的代码，直到基本情况n=1，我会得到一个错误，因为对于768=3*256和3，不能精确地除以2。如何仅为M(n(修复此问题？

Answer 1

让我们去掉一些细节，这样我们就可以专注于要点了。假设你有这个递归函数：

int foo(int n) {
std::cout << "foo(" << n << ")n";
// base case
if (n <= 1) return 1;
// recurse 
return foo( n-2 );
}

在5次递归之后，你想调用一些其他函数

int bar(int n){
std::cout << "bar(" << n << ")n";
return 42;
}

然后，您只需要添加一个参数来选择其他函数应该调用多少步，以及一个计数递归的计数器：

int foofoo(int n, int steps,int counter=1) {
std::cout << "foofoo(" << n << 'n';
if (counter == steps) return bar(n);
if (n <= 1) return 1;
foofoo(n-2,steps,counter+1);
}

然后

int main() {
foofoo(12,5);   
}

打印

foofoo(12)
foofoo(10)
foofoo(8)
foofoo(6)
bar(4)

PS:^是逐位异或，得到n的平方写n*n。