способ проверить, выполняете ли вы при первом запуске несколько рекурсивных вызовов c ++ - PullRequest
Новая
       6

способ проверить, выполняете ли вы при первом запуске несколько рекурсивных вызовов c ++

2 голосов
/ 17 ноября 2011

Мне было интересно, есть ли способ проверить, находится ли вы на первом рекурсивном вызове серии из множества рекурсивных вызовов.

Я работаю над функцией, которая проверяет,вход палиндром.После завершения последнего рекурсивного вызова входная строка изменяется на обратную по сравнению с исходной.Теперь все, что я хочу сделать, это сравнить результат с оригиналом.Но когда базовый случай достигнут, у меня больше нет доступа к копии исходной строки, которую я сделал в операторе else.

Тогда я думаю сравнить palCopy с palCheck в операторе else, но проблема в том, что программа проверяет это во время КАЖДОГО рекурсивного вызова, когда я хочу проверять его только при возврате элемента управленияна оригинальный рекурсивный вызов.Есть ли способ условно сравнивать palCopy и palCheck только тогда, когда элемент управления возвращается к исходному рекурсивному вызову? 

void isAPalindrome(MyString palCheck, int bound1, int bound2)
{

    if (bound1 >= bound2)
    {
        cout << palCheck;
    }
    else
    {
        MyString palCopy = palCheck;  // make a copy of the original argument so as not to alter it
        char temp = palCopy[bound1];
        palCopy[bound1] = palCopy[bound2];
        palCopy[bound2] = temp;
        isAPalindrome(palCopy, bound1 + 1, bound2 - 1); 
    }

Ответы [ 6 ]

2 голосов
/ 17 ноября 2011

Я бы не решил эту проблему таким образом, но не обращайте на это внимания.Общий способ сделать что-то вроде этого - переместить рекурсию в вспомогательную функцию, которая принимает дополнительный аргумент: 

static void 
is_palindrome_internal(string palCheck, int bound1, int bound2,
                       bool outermost)
{
   ...
   is_palindrome_internal(..., false);
   ...
}

void
is_palindrome(string palCheck, int bound1, int bound2)
{
   is_palindrome_internal(palCheck, bound1, bound2, true);
}

Тогда outermost будет истинным, только если текущий вызов является внешним.Этот подход также имеет то преимущество, что вы можете скрыть аргументы bound1 и bound2 от общедоступного API (разумеется, только если вы не хотите работать с подстроками). 

void
is_palindrome(string palCheck)
{
    is_palindrome_internal(palCheck, 0, palCheck.length(), true);
}
2 голосов
/ 17 ноября 2011

В общем, вы можете отслеживать глубину рекурсии, выполнив что-то вроде: 

void recurse(int value, const int depth=0)
{
     recurse(value, depth+1); 
}

То есть используется дополнительная переменная для каждого из вызовов, которая записывает глубину рекурсии в любой заданной точке.

1 голос
/ 17 ноября 2011

C ++ не имеет примитивного способа узнать, находитесь ли вы в первой рекурсии. Но вы можете использовать переменную level, которая считает глубину рекурсии. Что-то вроде: 

void isAPalindrome(MyString palCheck, int bound1, int bound2, int level=0)
{
    if (bound1 >= bound2)
        cout << palCheck;
    else
    {
        MyString palCopy = palCheck;
        char temp = palCopy[bound1];
        palCopy[bound1] = palCopy[bound2];
        palCopy[bound2] = temp;
        isAPalindrome(palCopy, bound1 + 1, bound2 - 1, level+1);
        if (level == 0)
            // You are in the first recursion call
    }
}
1 голос
/ 17 ноября 2011

Вы уже передаете одну копию строки в качестве аргумента. Вы также можете передать ссылку на исходную строку, чтобы все уровни рекурсии имели доступ к обоим. 

void isAPalindrome(MyString palCheck, int bound1, int bound2 , const MyString& original )
{
//Do stuff

     isAPalindrome(palCopy, bound1 + 1, bound2 - 1,original); 
}
0 голосов
/ 17 ноября 2011

Я бы использовал локальную структуру, так что is_palindrome() примет только один аргумент: 

bool is_palindrome(const std::string& s) 
{
   struct local
   {
      static bool is_palin(const std::string& s, int l, int h) 
      {
         return l>= h?true:(s[l] == s[h]? is_palin(s,l+1,h-1):false);
      }
   };
   return local::is_palin(s, 0, s.size() - 1);
}

Демонстрация в сети: http://www.ideone.com/o1m5C

Используйте и изменяйте ее в зависимости от того, что вы хотите.

0 голосов
/ 17 ноября 2011

Сделайте это отдельной функцией: 

void isAPalindromeHelper(MyString& palCheck, int bound1, int bound2)
{
    if (bound1 >= bound2)
    {
        cout << palCheck;
    }
    else
    {
        char temp = palCopy[bound1];
        palCopy[bound1] = palCopy[bound2];
        palCopy[bound2] = temp;
        isAPalindromeHelper(palCopy, bound1 + 1, bound2 - 1); 
    }
}
void isAPalindrome(MyString palCheck)
{
    MyString palCopy = palCheck;  
    isAPalindromeHelper(palCheck, 0, palCheck.size()); 
    if (palCopy == palCheck)
        //newstuff here
}
...