Объяснить конструкцию и ход работы

Question

Я понимаю конструкцию if (*(s+1)), указатель на следующий элемент массива, пока тот не станет равняться NULL, но вот почему функция возвращает реверс массива никак не пойму. Объясните пожалуйста.

void reverse(const char* s) {
    if (*(s + 1))
        reverse(s + 1);
    std::cout << *s;
}
int main() 
{ 
    char Arr[100] = {"Я изучаю язык программирования С++"};
    reverse(Arr);
    return 0;
}

Answer 1

Ну смотрите, пока есть символы, они вносятся в стек, как локальные переменные-аргументы. А потом выводятся по одному. Но вывод выполняется уже после того как все символы в стеке...

Пусть строка abc

В переменной сохраняется указатель на a, рекурсивно вызывается функция для b. Она сохраняется в переменной, рекурсивно вызывается функция для c. Она сохраняется в переменной, рекурсивно НЕ вызывается функция для нулевого символа — просто возврат.

Выводится символ для последнего вызова, т.е. с. Выход из функции, возврат во второй вызов, для b. Выводится b, выход из функции, возврат в первый вызов, для a. Вывод a. Полный выход из рекурсии.

Так понятнее?

Answer 2

Это обычная рекурсия. Попробуйте вручную пройти код на какой-то короткой строке, например, длиной в три символа.

Смотрите, что получается.

Строка всегда заканчивается нулем.

Сначала вызывается функция reverse на строке из трех символов. Проверяет, что следующий (второй) символ строки не ноль, и вызывает сама себя на строке из двух символов.

Снова проверяет следующий символ - не ноль. Вызывает себя же на строке из одного символа. Проверят - следующий символ ноль. Тогда выполняет вывод текущего (последнего) символа строки и возвращает управление в точку вызова. То есть себе же, но на предыдущем шаге рекурсии. Там осуществляет вывод текущего для этого шага (предпоследнего) символа строки, и снова возврат на предыдущий шаг.

В конце концов выводит первый символ строки, и возвращается в функцию main

Answer 3

Одна картинка вместо тысячи слов. Добавим отладочную печать:

#include <iostream>

void reverse(const char* s) {
    std::cerr << "enter reverse(\"" << s << "\")\n";
    if (*(s + 1))
        reverse(s + 1);
    // std::cout << *s;
    std::cerr << "print '" << *s << "'\n";
    std::cerr << "leave reverse(\"" << s << "\")\n";
}

int main() { 
    reverse("Learn C++");
}

$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror temp.cpp && ./a.out 
enter reverse("Learn C++")
enter reverse("earn C++")
enter reverse("arn C++")
enter reverse("rn C++")
enter reverse("n C++")
enter reverse(" C++")
enter reverse("C++")
enter reverse("++")
enter reverse("+")
print '+'
leave reverse("+")
print '+'
leave reverse("++")
print 'C'
leave reverse("C++")
print ' '
leave reverse(" C++")
print 'n'
leave reverse("n C++")
print 'r'
leave reverse("rn C++")
print 'a'
leave reverse("arn C++")
print 'e'
leave reverse("earn C++")
print 'L'
leave reverse("Learn C++")

Псевдокод для функции: "напечатать строку значит напечатать хвост строки, напечатать её первый символ". Очевидно, что первый символ строки печатается последним. На человеческом языке - строка печатается задом-наперед.

БЛОГ НА HUSL

Объяснить конструкцию и ход работы

Ответы (3 шт):