Рекурсия с C ++

Question

Я изучаю рекурсию в моем текущем классе, и эта идея немного сложна для меня. Насколько я понимаю, когда мы создаем функцию, она будет выполняться столько раз, пока не будет удовлетворен наш "базовый вариант". Мне интересно, как это выглядит и возвращается в стек. Для примера я написал следующую функцию для простой программы, чтобы подсчитать, сколько раз di git отображается в целом числе.

Что это выглядит и работает в представлении стекового фрейма? Я не совсем понимаю, как работает возвращение. Я ценю помощь!

int count_digits(int n, int digit) {
  // Base case: When n is a single digit.
  if (n / 10 == 0) {
    // Check if n is the same as the digit.
    // When recursion hits the base case it will end the recursion.
    if (n == digit) {
      return 1;
    } else {
      return 0;
    }
  } else {
    if (n % 10 == digit) {
      return (1 + count_digits(n / 10, digit));
    } else {
      return (count_digits(n / 10, digit));
    }
  }
}

Answer 1

Что это выглядит и работает в представлении стека? Я не совсем понимаю, как работает возвращение. Я ценю помощь!

Давайте попробуем построить решение снизу вверх.

1. Если бы вы вызвали функцию - int count_digits(int n, int digit) как count_digits(4, 4), что бы произошло?
   

Это базовый случай вашего решения, поэтому очень легко увидеть, что является возвращаемым значением. Ваша функция вернет 1.

Теперь давайте добавим еще один di git и вызовем функцию как- count_digits(42, 4). Что произойдет?

Ваша функция проверит последние значения di git, равные 2, и сравнит их с 4, поскольку они не равны, поэтому она вызовет функцию count_digits(4, 4) и все Возвращаемое значение, будет возвращено в результате count_digits(42, 4).

Теперь давайте добавим еще одну ди git и вызовем функцию наподобие - count_digits(424, 4). Что произойдет?

Ваша функция проверит последние значения di git, равные 4, и сравнит их с 4, поскольку они равны, поэтому она вызовет функцию count_digits(42, 4) и все, что возвращаемое значение будет возвращено путем добавления 1 к нему. Поскольку число 4 с в 424 равно 1 + число 4 с в 42. Результат count_digits(42,4) будет рассчитан точно так же, как и ранее.

Рекурсивная функция создает решение в нисходящем порядке. Если изначально есть n цифр, то ваш ответ (0 или 1 в зависимости от последней ди git) + ответ с n-1 цифрами. И этот процесс повторяется рекурсивно. Таким образом, ваш рекурсивный код уменьшает количество проблем на одну ди git за раз, и это зависит от результата немедленной подзадачи.

Вы можете использовать репетитора C ++ на сайте pythontutor.com для шага пошаговая визуализация стека кадра. http://pythontutor.com/cpp.html#mode = edit

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

Проверьте этот ответ stackoverflow для понимания, что такое стековый фрейм - Объясните концепцию стекового фрейма в двух словах

Проверьте этот ответ stackoverflow для понимания рекурсии - Понимание рекурсии

Если вам нужна дополнительная помощь, пожалуйста, дайте мне знать в комментариях.