Рекурсивная функция, которая использует статическую переменную

Question

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

Цель этой функции - сначала заполнить массив нечетной переменной, так что вы называете это fillAryOddFirst (ary, 13), а затем массив будет заполнен в следующем порядке [13, 11, 9,7, 5, 3, 1, 2, 4, 6, 8, 12]

void fillAryOddFirst(int ary[], int size) {
    static int pos;
    if (size <= 0) {
        return;
    }
    if(size % 2 != 0){
        ary[pos] = size;
        pos++;
    }
    fillAryOddFirst(ary, size-1);
    if(size % 2 == 0 ){
        ary[pos] = size;
        pos++;
    }    
    return;
}

Answer 1

Нет, нет способа сбросить локальную переменную static.

Если вы хотите иметь возможность сбросить ее, единственный вариант - сделать ее глобальной переменной, т.е. переместить ее объявление за пределыфункция.

---

Другая возможность - сделать его параметром, который вы передаете по ссылке:

void fillAryOddFirst(int ary[], int size, int &pos)
{
    if (size <= 0)
    {
        return;
    }
    if (size % 2 != 0)
    {
        ary[pos] = size;
        pos++;
    }
    fillAryOddFirst(ary, size - 1, pos);
    if(size % 2 == 0 )
    {
        ary[pos] = size;
        pos++;
    }    
}

void fillAryOddFirst(int ary[], int size)
{
    int pos = 0;
    fillAryOddFirst(ary, size, pos);
}

Answer 2

Если size нечетно, запишите первый элемент. Если оно четное, напишите последний элемент. В любом случае, рекурсивно «фокусируйтесь» на оставшемся подмассиве:

void fillAryOddFirst(int ary[], int size) {
    if(size > 0) {
        if(size % 2 == 1) {
             // +---+---|...|---+
             // | s | ? |???| ? |
             // +---+---|...|---+
             // ^ ary           ^ ary + size
             //     ^ ary + 1   ^ (ary + 1) + (size - 1)
             //     \-----------/ focus on this range
             ary[0] = size;
             fillAryOddFirst(ary + 1, size - 1);
        } else /*if(size % 2 == 0)*/ {
             // +---|...|---+---+
             // | ? |???| ? | s |
             // +---|...|---+---+
             // ^ ary           ^ ary + size
             // |           ^ ary + (size - 1)
             // \-----------/ focus on this range
             ary[size - 1] = size;
             fillAryOddFirst(ary, size - 1);
        }
    }
}

Если записать в виде цикла, это будет

void fillAryOddFirst(int ary[], int size) {
    for(; size > 0; size--) {
        if(size % 2 == 1) *ary++ = size;
        else ary[size - 1] = size;
    }
}

То есть вы перебираете sizeвплоть до 1 и размещения коэффициентов в начале и четных в конце.

Answer 3

"... есть хороший способ сделать это без использования статической переменной."

Да. Обертывание функции в классе.

В классе переменная функции static int pos может стать простым атрибутом данных оболочки.

Ниже приведены несколько примеров кода.

1) Во-первых, нужно продемонстрировать, что ваша проблема повторяется.

2) Простая оболочка класса с именем class FillAryOddFirstClass_t. Функция очень похожа на исходную, но pos не является статичной.

3) Простая оболочка Functor, называемая классом FillAryOddFirstFunctor_t. Функторы имеют более простой вызов.

4) Поскольку вы объявили этот пост как вопрос C ++, элемент 4 использует вектор вместо массива - НО обратите внимание, что код использует тот же класс для запуска рекурсии, какэлемент 2, FillAryOddFirstClass_t, который ожидает массив! Векторные данные находятся в динамической памяти, и, указав "& iVec [0] '(вместо ary), переданный адрес является начальным элементом векторных данных в куче.

5) Это элемент 2 сДоп. класс FillAryOddFirstClass2_t внутренне сложен с двумя функциями отчета. Функции отчета строят строки для отображения хода выполнения рекурсии / отклонения.

---

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

#include <iomanip>
using std::setw;

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

#include <vector>
using std::vector;


// original - with static
void fillAryOddFirst ( int ary[], int size )
{
   static int pos;   // <<<<<<<<<<<<<<< static

   if (size <= 0) { return; }

   if(size % 2 != 0) { ary[pos] = size; pos++; }

   fillAryOddFirst(ary, size-1);

   if(size % 2 == 0 ) { ary[pos] = size; pos++; }

   return;
}

// class wrapper 
class FillAryOddFirstClass_t  // UDT - user defined type
{
   int pos;    // <<<<<<<<<<<<<<<  not static, a simple attribute

public:
   FillAryOddFirstClass_t() : pos (0) { }
   ~FillAryOddFirstClass_t() = default;

   void fillAryOddFirst ( int ary[], int indx )
      {
         if (indx <= 0) { return; }

         if(indx % 2 != 0) { ary[pos] = indx; pos++; }

         fillAryOddFirst(ary, indx-1);

         if(indx % 2 == 0 ) { ary[pos] = indx; pos++; }

         return;
      }
};

// Functor wrapper
class FillAryOddFirstFunctor_t // UDT (user defined type)
{
   int pos;    // <<<<<<<<<<<<<<<  not static

public:
   // default ctor and dtor do nothing, cost nothing

   void operator()( int ary[], int indx) // functor entry
      {
         pos = 0;  // init
         fillAryOddFirst(ary, indx);
         return;
      }

private:
   void fillAryOddFirst( int ary[], int indx) 
      {
         if (indx <= 0) { return; }

         if(indx % 2 != 0) { ary[pos] = indx; pos++; }

         fillAryOddFirst(ary, indx-1);

         if(indx % 2 == 0 ) { ary[pos] = indx; pos++; }

         return;
      }
};

// class wrapper, with cout progress indicator
class FillAryOddFirstClass2_t  // UDT
{
   int    pos;    // <<<<<<<<<<<<<<<  no static
   size_t sz = 10;

public:
   FillAryOddFirstClass2_t() : pos (0) { }
   ~FillAryOddFirstClass2_t() = default;

   void fillAryOddFirst ( size_t rLvl, int ary[], int indx )
      {
         if (indx <= 0) {
            cout << "\n\n" << setw(11)  << " " << "recurse end - decurse begins\n";
            return;
         }

         if(indx % 2 != 0) { ary[pos] = indx; pos++; }

         cout << rprtR   (rLvl,   ary); // recurse report

         fillAryOddFirst (rLvl+1, ary, indx-1);

         cout << rprtD   (rLvl,   ary); // decurse report

         if(indx % 2 == 0 ) { ary[pos] = indx; pos++; }

         return;
      }

   // report recurse
   string rprtR ( size_t rLvl, int ary[])
      {
         std::stringstream ssOut;
         ssOut << "\n  " << setw(4) << rLvl
               << "   " << show(ary) << ' ';
         return ssOut.str();
      }

   // report decurse
   string rprtD ( size_t rLvl, int ary[])
      {
         std::stringstream ssOut;
         ssOut << "\n  " << setw(4) << rLvl
               << "   " << show(ary) << '_';
         return ssOut.str();
      }

   string show(int ary[])
      {
         std::stringstream ssOut;
         for (uint i=0; i<(sz-1); ++i)
            if (ary[i])
               ssOut << "  " << ary[i];
         return ssOut.str();
      }

}; // class FillAryOddFirstClass2_t

Ниже приведен main (), который иллюстрирует, как каждыйиспользуется функция заполнения:

int main()
{
   const size_t sz = 9;
   {
      cout << "\n\n  Test1: original (function with static int pos)  \n";

      int ary[sz];       // automatic memory array
      init(&ary[0], sz); // function to fill ary with 0's
      show(&ary[0], sz);

      // this function uses static int pos
      fillAryOddFirst (&ary[0], sz);
      show(&ary[0], sz);
   }

   {
      cout << "\n\n  Test2: class wrapper (no static)\n";

      int ary[sz];
      init(&ary[0], sz);
      show(&ary[0], sz);

      {
         FillAryOddFirstClass_t faofObj;
         faofObj.fillAryOddFirst(&ary[0], sz);
      }
      show(&ary[0], sz);
   }

   {
      cout << "\n\n  Test3: Functor Wrapper (no static)\n";

      int ary[sz];  init(&ary[0], sz);
      show(&ary[0], sz);

      // no static int pos
      FillAryOddFirstFunctor_t()(&ary[0], sz);
      show(&ary[0], sz);
   }

   {
      cout << "\n\n  Test4: class, uses vector, not array (no static)\n";

      vector<int> iVec;
      for (uint i=0; i<sz; ++i) iVec.push_back(0); // vector grows
      show(&iVec[0], sz);

      {
         FillAryOddFirstClass_t faof;
         faof.fillAryOddFirst(&iVec[0], sz);
      }
      show(&iVec[0], sz);
   }

   {
      cout << "\n\n  Test5: class2 (no static) with graphic\n";

      vector<int> iVec;
      for (uint i=0; i<sz; ++i) iVec.push_back(0); // vector grows
      show(&iVec[0], sz);

      {
         cout << "\n    rlvl";
         FillAryOddFirstClass2_t faof2;
         faof2.fillAryOddFirst(1, &iVec[0], sz);
         cout << "\n    rlvl";
      }
      cout <<  "\n\n      ";
      show(&iVec[0], sz);
   }

   cout << endl;
   return 0;
}

Выход:

  Test1: original (function with static int pos)  
     0  0  0  0  0  0  0  0  0
     9  7  5  3  1  2  4  6  8


  Test2: class wrapper (no static)
     0  0  0  0  0  0  0  0  0
     9  7  5  3  1  2  4  6  8


  Test3: Functor Wrapper (no static)
     0  0  0  0  0  0  0  0  0
     9  7  5  3  1  2  4  6  8


  Test4: class, uses vector, not array (no static)
     0  0  0  0  0  0  0  0  0
     9  7  5  3  1  2  4  6  8


  Test5: class2 (no static) with graphic
     0  0  0  0  0  0  0  0  0

    rlvl
     1     9 
     2     9 
     3     9  7 
     4     9  7 
     5     9  7  5 
     6     9  7  5 
     7     9  7  5  3 
     8     9  7  5  3 
     9     9  7  5  3  1 

           recurse end - decurse begins

     9     9  7  5  3  1_
     8     9  7  5  3  1_
     7     9  7  5  3  1  2_
     6     9  7  5  3  1  2_
     5     9  7  5  3  1  2  4_
     4     9  7  5  3  1  2  4_
     3     9  7  5  3  1  2  4  6_
     2     9  7  5  3  1  2  4  6_
     1     9  7  5  3  1  2  4  6  8_
    rlvl

           9  7  5  3  1  2  4  6  8