Рекурсия и статические переменные

Итак, я готовился к вступительному экзамену здесь, в Индии, когда я наткнулся на этот кусок кода C

#include <stdio.h>
int main(void) {
    static int i = 4;
    if (--i) {
        main();
        printf("%d", i);
    }
}

Я думал, что инструкция printf никогда не будет выполнена, и результат будет пустым. Но я видел ответ 0000 и что это происходит из-за ключевого слова static с int.

Может ли кто-нибудь объяснить, почему printf выполняет или этот парень ошибается?

Ответы

Ответ 1

Может ли кто-нибудь объяснить, почему printf выполняет или этот парень ошибается?

Потому что возвращается main.

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

Поскольку переменная static, перед первым вызовом переменная объявляется и устанавливается в 4. Поскольку это static, одна и та же переменная будет использоваться каждый раз. Он просто пропускает декларацию и инициализацию, если вызывается снова (или, вероятно, даже в первый раз, поскольку переменные static могут быть выделены перед запуском).

В первом вызове переменная уменьшается до 3. 3 является правдивым значением, поэтому мы делаем блок if. Это вызывает main рекурсивно.

В этом втором вызове переменная уменьшается до 2. 2 по-прежнему правдива в C. Мы снова вызываем main снова.

В этом третьем вызове переменная уменьшается до 1. 1 по-прежнему остается правдой. Мы снова возвращаемся к main.

В этом четвертом вызове переменная уменьшается до 0. 0 false в C. Мы не вводим блок if. Мы не возвращаемся. Мы не печатаем. В этом вызове нечего делать main. Он возвращается в конце.

Теперь мы возвращаемся к третьему звонку. Мы только что вернулись с вызова на main. Мы все еще находимся внутри блока if. Следующий оператор - printf. Значение переменной теперь равно 0. Итак, мы печатаем 0. Ничего не оставалось делать, мы возвращаемся в конце.

Теперь мы вернулись во второй раз. Тем не менее 0, поэтому мы печатаем еще один и возвращаем.

Теперь мы вернулись к первому звонку. Тем не менее 0, поэтому мы печатаем еще один и возвращаем.

Мы напечатали 0 три раза, поэтому 000

Как вы заметили, по пути вниз мы не печатаем. Мы печатаем на обратном пути. К этому времени переменная равна 0. И мы вводим затем блок if три раза. Поэтому мы возвращаемся, а затем печатаем три раза.

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

Возможно, вам захочется подумать о том, как следующие три части кода будут реагировать по-разному:

void recurse() {
    static int i = 4;
    if (--i) {
        recurse();
        printf("%d", i);
    }
}

Распечатывает 000 при вызове в первый раз. После этого ничего не происходит.

void recurse(int i) {
    if (--i) {
        recurse(i);
        printf("%d", i);
    }
}

Будет напечатан 123, если он называется recurse(4). В качестве параметра мы имеем дело с другим i каждый раз, когда вызывается функция.

void recurse(int i) {
    if (--i) {
        printf("%d", i);
        recurse(i);
    }
}

Печатает 321, если вызывается как recurse(4). Печать по пути вниз, а не при возврате.

void recurse(int i) {
    printf("%d", i);
    if (--i) {
        recurse(i);
    }
}

Печатает 4321, если вызывается как recurse(4). Он печатает на пути вниз, а не вверх.

void recurse() {
    static int i = 4;
    printf("%d", i);
    if (--i) {
        recurse();
    }
}

Будет напечатан 4321. Мы печатаем по пути вниз, а не вверх. Обратите внимание, как параметр и переменная static дают такой же результат. Однако, если это называется во второй раз, он ничего не сделает. Параметр снова напечатает то же самое.

void recurse() {
    int i = 4;
    if (--i) {
        recurse();
        printf("%d", i);
    }
}

Петли навсегда. Без static каждый раз мы делаем новый i. Это будет работать до тех пор, пока не перегрузит стек и не сработает. Нет вывода, потому что он никогда не попадает в printf.

Самый простой способ проверить это - пойти куда-нибудь, как ideone.com, и запустить код. Спросить, почему он печатает что-то, является разумным для этого сайта. Но спрашивать, что он печатает, - это то, на что вы должны ответить самим.

Ответ 2

В контексте вопроса о рекурсии он распечатает "000" (я не знаю, почему ответ показывает 4 нуля, потому что с -i "декремент происходит до назначения" ). Если вы разворачиваете звонки, которые вы получаете:

if (--i) { //i == 3
    if (--i) { //i == 2
        if (--i) { //i == 1
            if (--i) { //i == 0
                // rest does not get evaluated since the condition is false
            }
            printf("%d", i); // i is 0 now
        }
        printf("%d", i); //i is still 0
    }
    printf("%d", i); //i is still 0
}

Однако, как большинство из них упомянули, этот код отстой, и я бы посоветовал вам никогда не рассматривать этот уровень неряшливости для любого программного обеспечения, которое вы пишете.

Ответ 3

Законно возвращаться на main в C * (хотя зачем вам?)

Кроме того, в C11 (5.1.2.2.1) говорится:

Он должен быть определен с типом возврата int... [или] Если тип возврата несовместим с int, статус завершения, возвращенный в среду хоста, не указан.

(С++ утверждает, что возвращаемый тип должен быть int)

Таким образом, эта часть кода на самом деле стандартно-совместима, но фактический доход определяется реализацией (спасибо @chux)

Может ли кто-нибудь объяснить, почему printf выполняет или этот парень ошибается?

Если вы компилируете C с помощью компилятора С++, парень ошибается. В противном случае код будет скомпилирован.

Теперь, когда это не работает, printf действительно будет выполняться, потому что переменная static инициализируется только один раз, согласно 6.2.4/3

Объект, чей идентификатор объявлен [...] с Спецификатор класса хранения static имеет статическую продолжительность хранения. Его срок службы - это весь выполнение программы и ее сохраненное значение инициализируется только один раз, до программы запуск

* Это определенно НЕ является законным в С++. Из [basic.start.main]:   "Основная функция не должна использоваться в программе". В этом ответе много ответов на С++, потому что вопрос был первоначально помечен как С++, и информация полезна

Ответ 4

В этом коде есть несколько проблем:

  • <stdio.h> не входит, вызов printf("%d", i); имеет поведение undefined.

  • Прототипом main без аргументов является int main(void). Определение main как void main() не переносимо и некорректно на некоторых платформах. Всегда используйте стандартные прототипы для main и возвращайте действительный статус выхода для хорошего стиля.

  • Плохой стиль для рекурсивного вызова функции main в C, и он имеет поведение undefined в С++.

Игнорируя тот факт, что поведение undefined означает, что все может случиться, в том числе индийские фирмы, использующие ужасающие тесты программирования, причина, по которой программа печатает 0000, вы, вероятно, ошибаетесь в тесте if (i--) или неправильно устанавливаете фигурные скобки из памяти, или парень просто ошибается. Функция main вызывает себя рекурсивно 3 раза, декрементируя одну и ту же переменную i каждый раз, пока она не станет 0, и каждый экземпляр печатает значение i, а именно 0, прежде чем он вернется к своему вызывающему, включая начальную вызов main().

static int i = 4; внутри функции определяет глобальную переменную i с начальным значением 4, доступ к которой возможен только внутри блока, где он определен. Все рекурсивные экземпляры main получают доступ к одной и той же переменной.

Ответ 5

Абстрактное качество и название этой функции.

Все переменные static инициализируются только один раз во время запуска программы и остаются его значением.

Когда процедура запуска вызывает main в первый раз, переменная i имеет значение 4. Затем вы уменьшаете ее значение до 3 и снова вызываете main. На этот раз значение i равно 3 Затем вы уменьшите его значение до 2......