2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Помогите понять странность в рекурси
Сообщение28.02.2011, 00:27 
Аватара пользователя
Вот игрался рекурсией
Код:
    class Program
    {
        static uint i = 0;
        static void Main()
        {
            i++;
           
            Console.WriteLine("Вызван метод Main {0} раз", i);
            if (i > 1000)
            {
                return;
            }

            Main();
            Console.WriteLine("Освобождение метода № {0}", i);
            i--;
            if (i < 4)
                Main();
        }
    }
}

Здесь количество вызванных методов волнообразно. И что интересно, так то, что нижняя цифра воле i в ифе (4) указывает на то, сколько будет волн. От куда программа знает какая это волна, если i, как говорит дебагер, в каждой волне одинаково?

 
 
 
 
Сообщение11.03.2011, 05:31 
2Inafalutamen
Насколько я понимаю, "волной" назван такой кусок вывода программы:
Код:
Вызван метод Main 1 раз
[или "Вызван метод Main 5 раз", если это не первая волна]
Вызван метод Main 2 раз
...
Вызван метод Main 1001 раз
Освобождение метода № 1001
Освобождение метода № 1000
...
Освобождение метода № 4
["Освобождение метода № 5", если волна последняя]


Всего таких волн будет 4 (хотя задача параметризуется, т.е. вместо 1000 и 4 можно использовать переменные). Видимо, рассуждения ваши таковы: количество волн можно подсчитать, заметив, что, во-первых, код до if(i<4) Main() вызывает формирование одной волны, при этом сначала i=1 и в конце i=3 (второй по тексту рекурсивный вызов не будет выполняться на всех уровнях рекурсивной вложенности -- из-за условия i<4); а во-вторых, код void Main(){... if(i<4) Main();} эквивалентен коду void Main(){do ... while(i<4);} (т.н. концевая рекурсия), который с очевидностью выполняется 4 раза (в результате будет 4 волны).

Поэтому странно, что код до последнего условия оставляет после себя i=3, как бы предсказывая то, что записано в последнем условии (i<4).

Как надо здесь рассуждать? Видно, что код до первого (по тексту) рекурсивного вызова включительно формирует первую "полуволну", и понятно, что при этом будет выведено ровно тысяча и одно сообщение "Вызван метод Main ... раз". На максимальной рекурсивной глубине теперь произойдет вывод сообщения "Освобождение метода № ..." и если i не меньше 4 (видите, второй по тексту рекурсивный вызов на глубоких слоях рекурсии обходится исключительно из-за условия i<4), то мы попадаем на предыдущий уровень рекурсивной вложенности, опять выводя сообщение "Освобождение метода № ..." и т.д.

Как только достигается i<4, так сразу же запускается вторая волна. Заметьте, что впервые условие i<4 выполняется вовсе не на первом уровне рекурсии (то есть не в том "экземпляре", который был вызван при старте программы), а именно на четвертом уровне глубины. Также важно понимать, что вторая волна начинает выполняться с i=4. Это кажется тривиальным фактом, но дает разгадку! Действительно, раз мы начинаем с i=4, то хотя для каждого инкремента i++ есть симметричный ему декремент i--, но i не сможет стать при этих декрементах меньше чем 4. А значит условие i<4, приводящее ко второму (по тексту) рекурсивному вызову уже выполниться не сможет.

Теперь вспомним, что сейчас рассматривалась вторая волна, которая была запущена при первом же срабатывании i<4 и произошло это на четвертом уровне вложенности. Поэтому, после отработки второй волны мы по-привычке вываливаемся на предыдущий уровень рекурсии, а именно на третий. Там тоже будет, на этот раз уже третья волна. И так будет продолжаться до самого первого уровня. То есть, волны будут пускаться на четвертом, третьем, втором и первом уровнях -- всего 4 волны.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group