Понимание порядка выполнения рекурсивных функций

Question

template <typename T>
T sum(stack<T>& s){
    if (s.empty()){
        return 0;
    } else {
        T first = s.top();
        s.pop();
        T total = sum(s)+first;
        s.push(first);
        return total;
        }
}

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

Как вы увидите, данный код работаетоднако я не понимаю поток управления или последовательность выполнения рекурсивных вызовов и операторов возврата. Когда я вижу этот код, я понимаю, как элементы суммируются, однако я не понимаю, как вызов s.push (first) добавляет в стек всех элементов. Я с трудом оборачиваюсь головой, почему бы он не выдвинул только последний элемент стека, а затем вернул итог.

Мое текущее понимание того, почему это работает, является неполным и, вероятно, ошибочным, и заключается в следующем: поскольку каждый оператор return возвращается к самой последней вызывающей программе, когда рекурсия достигает базового случая и завершается, операторы return будут работатьобратно в стек рекурсивных вызовов до тех пор, пока он не доберется до исходной вызывающей стороны и, следовательно, при каждом движении обратно в стек выполняет s.push ().

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

Answer 1

Ваше общее понимание верно. Вам не хватает только подключения последних точек.

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

Это поможет понять, если вы пометите каждый рекурсивный вызов. Давайте назовем начальный вызов рекурсивной функции "A". Когда рекурсивная функция вызывает себя рекурсивно, вызовите этот вызов рекурсивной функции "B". Затем он снова звонит, и это "C". Затем следует «D» и т. Д.

Ключевым моментом, который необходимо понять, является то, что когда функция возвращается, она возвращается туда, откуда она была вызвана. Таким образом, «D» возвращается к «C», что возвращает к «B», и возвращается к «A».

Теперь рассмотрим вашу рекурсивную функцию. Когда у стека осталось одно значение, назовем его «D», он удаляет значение «D» из стека и выполняет рекурсивный вызов «E», который обнаруживает, что стек пуст.

Таким образом, он возвращается к «D», что возвращает значение «D» обратно в стек, который теперь снова имеет одно значение. Затем он возвращается к «C», что возвращает значение «C» обратно в стек, который теперь содержит два исходных, последних значения в стеке, в том же порядке.

Inтаким образом, вызовы функции раскручиваются в обратном порядке по сравнению с их исходной последовательностью вызова, восстанавливая стек точно таким, каким он был изначально.

Answer 2

"Если кто-то может выложить последовательность выполнения ..."

Всегда разрешается добавлять (сменные) метки в исполняемый код. Следующее иллюстрирует один подход.

Примечание 1. Для упрощения я удалил проблемы с шаблонами. Демонстрация использует int.

Примечание 2: dumpStack не является рекурсивным.

Примечание 3: m_stck является атрибутом данных класса, поэтому его не нужно передавать из sumStack в sumStack.

#include <iostream>
using std::cout, std::endl; // c++17

#include <iomanip>
using std::setw, std::setfill;

#include <string>
using std::string, std::to_string;

#include <stack>
using std::stack;

#ifndef                 DTB_PCKLRT_HH
#include "../../bag/src/dtb_pclkrt.hh"
using  DTB::PClk_t;
#endif



class StackW_t   // stack wrapper UDT (user defined type)
{
private:
   int         m_N;     // max elements
   stack<int>  m_stck;  // default ctor creates an empty stack

public:
   StackW_t(int  N = 10) // simple default size
      {
         m_N = N;          // capture
         assert(m_N > 1);  // check value
         for (int i=0; i<m_N; ++i)
            m_stck.push(N - i);  // simple fill
      }

   ~StackW_t() = default; // dtor default deletes each element of m_stck

   // recurse level-vvvv
   int sumStack(int rLvl = 1)
      {
         if (m_stck.empty())
         {
            cout << "\n" << setw(2*rLvl) << " " << setw(4) << "<empty>";
            return 0;
         }
         else
         {
            int first = m_stck.top();                      // top element
            m_stck.pop();                                  // remove top element

            cout << "\n" << setw(2*rLvl)
                 << " " << setw(4) << first;               // recurse report

            // use first value then recurse into smaller stack with next rLvl
            int sum = first  +  sumStack(rLvl+1);

            cout << "\n" << setw(2*rLvl)                   // decurse report
                 << " " << setw(3) << "(" << first << ")";

            m_stck.push(first);                            // restore element after use
            return sum;
         }
      }

   void dumpStack(string lbl, int rLvl = 1)
      {
         stack<int>  l_stck = m_stck; // for simplicity, use copy of

         cout << "\n  dumpStack " << lbl << setw(2*rLvl);
         while (!l_stck.empty())
         {
            cout << " " << " " << l_stck.top();
            l_stck.pop();  // remove displayed member
         }
         cout << "\n";
      }
}; // class StackW_t


// Functor 829
class F829_t // use compiler provided defaults for ctor and dtor
{
   PClk_t  pclk; // posix clock access

public:
   int operator()(int argc, char* argv[]) { return exec(argc, argv);  }

private:

   int exec(int  , char** )
      {
         int retVal = 0;

         // create, auto fill with value 1..10
         StackW_t stk;

         stk.dumpStack("before"); // invoke display

         cout << "\n  stk.sumStack():  ";

         uint64_t start_us = pclk.us();

         // invoke recursive compute, start at default rLvl 1
         int sum = stk.sumStack();

         auto  duration_us = pclk.us() - start_us;

         cout << "\n  sum:  " << sum << endl;

         stk.dumpStack("after"); // invoke display

         cout << "\n  F829_t::exec() duration   "
              << duration_us << " us    (" <<  __cplusplus  << ")" << std::endl;
         return retVal;
      }

}; // class F829_t

int main(int argc, char* argv[]) { return F829_t()(argc, argv); }

---

Примечание 4: при рекурсии rLvl увеличивается, поэтому значение сдвигается вправо для каждой строки

Примечание 5: во время дециметра rLvl восстанавливается при возврате функции,таким образом, вывод также восстанавливается до выравнивания

Примечание 6: до и после стека показывает успешное восстановление стека

Выход:

  dumpStack before   1  2  3  4  5  6  7  8  9  10

  stk.sumStack():  
     1
       2
         3
           4
             5
               6
                 7
                   8
                     9
                      10
                      <empty>
                      (10)
                    (9)
                  (8)
                (7)
              (6)
            (5)
          (4)
        (3)
      (2)
    (1)
  sum:  55

  dumpStack after   1  2  3  4  5  6  7  8  9  10

Answer 3

Ваша функция выглядит примерно так:

if (s.empty()){
        return 0;
} else {
        T first = s.top();
        s.pop();
        T total = sum(s)+first;
        s.push(first);
        return total;
}

Чтобы посмотреть, как это работает, давайте представим, что это на самом деле макрос, и расширим функцию до того, что обычно выполняется:

if (s.empty()){
        return 0;
} else {
        T first = s.top();
        s.pop();
        T total = if (s.empty()){
                return 0;
            } else {
                T first = s.top();
                s.pop();
                T total = sum(s)+first;
                s.push(first);
                return total;
        }+first;
        s.push(first);
        return total;
}

Это, конечно, только пример. Поскольку это не макрос, это не то, что действительно происходит. Это просто для иллюстрации.

Однако дело в том, что код в вашей функции будет выполняться каждый раз, когда вы вызываете функцию аналогично второму фрагменту кода. Таким образом, в конечном итоге происходит то, что самая внутренняя функция перемещается в стек, а затем вызывающая функция перемещается в стек и т. Д., Пока все не будет перенесено обратно в стек. Таким образом, даже если в стек выполняется один вызов, он будет выполняться каждый раз при выполнении функции.