Проблемы с созданием нехвостовой рекурсивной функции (новичок в c ++) - PullRequest
Новая
       9

Проблемы с созданием нехвостовой рекурсивной функции (новичок в c ++)

0 голосов
/ 19 октября 2019

Я работал над решением этой проблемы с обратной строкой и без хвостовой рекурсии C ++. Я смог успешно написать его, используя библиотеки (STL, strlen), но мне нужно уметь исправлять его с помощью только одного целого и одного символа в функции и без библиотек.

Это то, что янацеливание кода на внешний вид, но с функцией ReverseString, соответствующей определенным ограничениям. 

#include <iostream>

using namespace std;

// constant
const int STRING_AMOUNT = 100;

// protocol
int ReverseString(char*);

// main method
int main() {
  char theString[STRING_AMOUNT] = "abcde";
  cout << "The string is: " << endl;
  cout << theString << endl << endl;
  cout << "Reversing the Function" << endl;
  ReverseString(theString);
  cout << "The string contains: " << endl;
  cout << theString << endl;
  // exit program
  return 0;
}

int ReverseString(char* reverseString) {

}

1 Ответ

0 голосов
/ 19 октября 2019

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

Для нашего базового случая строка, которая является просто нулевым ограничителем '\0', всегда будет нулевой. 

if (*c == '\0') {
    return 0;
}

Начиная с "abcde", к которому в конце добавлен нулевой терминатор, мы не можем точно знать, когда закончится строка. Таким образом, мы считаем, что длина строки всегда будет на 1 больше, чем указатель, продвинутый на один шаг вперед, что приведет к тому, что символ * будет указывать на "bcde", и т. Д. 

return 1 + StringReverse(c + 1);

И этов значительной степени это для рекурсивной функции. 

int StringReverse(char *c) {
    if (*c == '\0') {
        return 0;
    }
    return 1 + StringReverse(c + 1);
}

Теперь это ничего не будет делать само по себе, внутренние вызовы функции не будут знать, где начало строки, чтобы допустить обмен ... кроме места, которое изначальновызвал его.

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

void ReverseString(char *start) {
    int size = StringReverse(start);

    // The swap code goes here...
}
...