c++ - 如何在特定级别停止递归函数并在其中插入另一个函数？

Question

我有2个问题:我有一个递归函数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:^是按位XOR，要获得n的平方，请编写n*n。