Как эта рекурсивная функция возвращает правильный ответ?

Question

Я хотел знать, как эта функция возвращает 4, что является правильным ответом, когда она сбрасывает переменную res каждый раз, когда функция вызывает себя. num = 2367319

int func(int num)
{
    int res = 0;
    if (num > 0)
        res = (num % 10 % 3 == 0 ? 1 : 0) + func(num / 10);

    return res;
}

Answer 1

res не "сброс". Скорее новая локальная переменная с именем res создается для каждого рекурсивного вызова.

Я предлагаю вам добавить несколько операторов printf(), чтобы увидеть, как работает эта функция.

Answer 2

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

Рассмотрим в следующем примере функцию foo() с некоторыми байтами локальных переменных, вызывающими bar() с некоторыми другими байтами локальной переменной. (Для простоты c цели я исключил адрес возврата функции из стека)

 /*stack growth in this direction ---->*/


 foo()-------+
             |
    /*foo code execution */
             | 
           bar()----------+
                          |
                  /* bar() Code execution */
                          | 
             +------------+
             |
|------------+

При вызове функций стек расширяется и сжимается при выходе из функции.

В случае рекурсивной функции bar() бывает foo() снова и снова. Но новое расположение стека выделяется для каждого вызова функции.

И, следовательно, в вашем случае res устанавливается в ноль в другом расположении стека, даже если кажется, что это одно и то же имя переменной.

Answer 3

Для начала декларация и реализация функции плохие.

Параметр функции имеет тип int. Таким образом, пользователь может ввести отрицательное число и будет ждать, сколько цифр числа делится на 3. Однако функция возвращает 0. Возникает вопрос: а что делать с отрицательными числами? Чтобы написать еще одну функцию?

Вторая проблема заключается в том, что функция не может обрабатывать целые числа типов long int и long long int. Опять же, нужно ли нам писать отдельные функции для этих целочисленных типов со знаком?

Функция использует избыточную переменную res.

Она может быть объявлена ​​и реализована следующим образом, как показано в демонстративном примере. Программа ниже ..

#include <stdio.h>

unsigned int func( long long int n )
{
    const long long int Base = 10;

    return n == 0 ? 0 : ( n % Base % 3 == 0 ) + func( n / Base );  
}

int main(void) 
{
    printf( "%d : %u\n", 2367319, func( 2367319 ) );
    printf( "%d : %u\n", -2367319, func( -2367319 ) );

    return 0;
}

Вывод программы:

2367319 : 4
-2367319 : 4

Как работает функция?

Если n равно 0, то функция возвращает 0 .

    return n == 0 ? 0 : ( n % Base % 3 == 0 ) + func( n / Base );  
           ^^^^^^   ^^

В противном случае, если последний ди git n % Base (остаток от деления на 10) числа делится на 3, тогда это выражение

    return n == 0 ? 0 : ( n % Base % 3 == 0 ) + func( n / Base );  
                          ^^^^^^^^^^^^^^^^^^

дает 1 (правда). В противном случае это дает 0. Таким образом, функция подсчитывает количество цифр, делимых на 3 таким образом, рекурсивно.

Например, давайте рассмотрим число 2367319.

Выражение 2367319 % 10 дает di git 9. 9 % 3 (2367319 % 10 % 3) равно 0. Таким образом, выражение

2367319 % 10 % 3 == 0

дает 1.

Теперь функция вызывает себя с числом 2367319 / 10, которое с номер 236731. И операция с последним di git этого нового номера повторяется. В этом случае выражение

236731 % 10 % 3 == 0

оценивается как 0 (false).

И так далее. Все результаты вызовов функций накапливаются и возвращаются.

Фактически у вас будет

(2367319 % 10 % 3 == 0) + (236731 % 10 % 3 == 0) + (23673 % 10 % 3 == 0) +...+ 0

         1              +         0              +        1              +...+ 0 

Answer 4

res равно количеству цифр, делимому на 3. Он всегда будет иметь правильное значение, пока num все еще больше 0.