Как я могу остановить рекурсивную функцию на определенном уровне и вставить туда другую функцию? - PullRequest
Новая
       31

Как я могу остановить рекурсивную функцию на определенном уровне и вставить туда другую функцию?

1 голос
/ 20 апреля 2020

У меня есть 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; 
 }

Я хотел бы запустить 5 уровней рекурсивной функции M для n = 768, а затем вставить функцию 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) в этом way.

Но я не мог организовать рекурсивный код таким образом. Может кто-то помочь мне с этим? Нужно ли преобразовывать M (n) в итеративную функцию для достижения моей цели или я могу просто исправить рекурсию? Если так, как я могу преобразовать в итеративную функцию?

Мой второй вопрос:

Если я запускаю код для M (n) до базового случая n = 1, я получаю ошибку, поскольку для 768 = 3 * 256 и 3 не делится на 2 точно. Как я могу это исправить только для M (n)?

1 Ответ

1 голос
/ 20 апреля 2020

Давайте избавимся от некоторых деталей, чтобы сосредоточиться на самом главном. Предположим, у вас есть эта рекурсивная функция: 

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.

...