Программа, взорвавшаяся после использования рекурсии

Question

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

Прошел мой код в Visual Studio и по какой-то причине окно просмотра скажет, что i равно длине строки (то есть завершающему условию выхода из цикла while). Я перешагиваю его в последний раз, и он говорит, что теперь я меньше длины строки. Затем он остается в цикле while навсегда.

Я знаю, что это звучит запутанно, поэтому приведу пример. Я вхожу в «Spongebob», и он делает все, что я хочу (т. Е. Говорит, что длина Spongebob равна 9, печатает «bobegnopS», увеличивает i до длины строки и т. Д.), Но затем он говорит, что i теперь 8 (т.е. только на 9) и никогда не выходит из цикла while.

Вот моя ReverseString функция():

void ReverseString(char * string, bool stringReversed, int stringLength, int i) 
{ 
    i++; 
    if(!stringReversed) 
    { 
     while(*string != '\0') 
     string++; 
    } 
    stringReversed = true; 

    while(i < stringLength) 
    { 
     string--; 
     std::cout << *string; 
     ReverseString(string, stringReversed, stringLength, i); 
    } 
    }  

Вот вызов:

case 3: 
    //Learn By Doing 16.6 
    { 
     char string[BUFFER_LENGTH]; 
     bool stringReversed = false; 

     int base = 0; 
     int exponent = 0; 

     std::cout << "\nEnter base: " << std::endl; 
     std::cin >> base; 

     std::cout << "\nEnter exponent: " << std::endl; 
     std::cin >> exponent; 

     //Print pow 
     NewLine(); 
     std::cout << base << " to the " << exponent << " is " << pow(base, exponent); 

     //Reverse string using recursion 
     std::cout << "\nEnter string: " << std::endl; 
     std::cin >> string; 


     NewLine(); 
     int stringLength = strlen(string); 
     int i = 0; 
     ReverseString(string, stringReversed, stringLength, i); 

    } 

Answer 1

void ReverseString(char * string, bool stringReversed, int stringLength, int i) 
{ 
    ... 
    while(i < stringLength) 
    { 
    string--; 
    std::cout << *string; 
    ReverseString(string, stringReversed, stringLength, i); 
    } 
} 

Ничто внутри цикла не изменяет i или stringLength (функция ReverseString принимает их по значению , а не по ссылке.) Таким образом, он никогда не может прекратиться.

Answer 2

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

n! = n * (n-1) *...*2*1 

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

int factorial(int n) 
{ 
    // stop when we reached 1 
    // otherwise we never finish 
    if(n == 1) return 1; 
    // now do the magic 
    return n * factorial(n - 1); 
} 

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