Изменить рекурсивную функцию на итеративную

Есть рекурсивная функция f(). Он просматривает cond, а затем либо возвращает, либо выполняет f(), а затем g(). Считайте cond внешней переменной, которую можно установить где-то еще, возможно, в другом потоке.

  1. Если первые пять раз проверяется cond, cond == true, а шестой раз, cond == false, опишите поток кода.

  2. Поскольку это рекурсивно, код может страдать от переполнения стека, если cond == true слишком долго. Заполните функцию iterative_f() так, чтобы поток кода был идентичен потоку кода в (1).

    //recursive
    
    void f()
    {
        if(cond == false)
            return;
        f();
        g();
    }
    
    //iterative  
    void iterative_f() {
    
    }
    

person tbag    schedule 08.04.2011    source источник
comment
Так грустно видеть учителей, поставляющих boolean_variable == false! Пожалуйста, используйте if (!cond) или if (not cond) (как эквивалентные, так и стандартные, хотя я не уверен, что даже MSVC++ 2010 поддерживает not - думаю, они слишком беспокоятся о нарушении кода, где люди не называли свою переменную).   -  person Tony Delroy    schedule 08.04.2011
comment
@Tony: not не является ключевым словом C.   -  person JeremyP    schedule 08.04.2011
comment
JeremyP: правда - только C++ - я должен был проверить теги вопроса :-/.   -  person Tony Delroy    schedule 08.04.2011


Ответы (1)


  1. Поскольку условие ложно в 6-й раз, функция будет выполняться 5 раз. В результате функция g будет выполнена 5 раз.

  2. Теперь вы можете написать итеративную функцию следующим образом:

    void iterative_f() 
    {
       while(cond)
       {
          g();
       } 
    }
person bala    schedule 08.04.2011
comment
Меня спросили об этом в интервью, и это был мой точный ответ. Однако интервьюер сказал, что эта итеративная функция изменит последовательность вызова функции g(). Как и в рекурсивной функции, сначала вызывается 5-й экземпляр функции g(). Однако эта итеративная версия сначала вызовет 1-й экземпляр. - person tbag; 08.04.2011
comment
Да, это может быть логичным аргументом. Но создание последовательности вызовов функции не может иметь представления о конкретном порядке. - person bala; 09.04.2011
comment
Давайте представим это проще. Для рекурсивной функции мы не вызываем сначала 5-й экземпляр функции g(), но мы вызываем функцию g() в первый раз при 5-м вызове функции f(). Что касается итерационной функции, то мы вызываем функцию g() впервые на первой итерации. Имеет ли это смысл? - person bala; 09.04.2011