Непонимание возврата в этой рекурсивной функции (C ++) - PullRequest
Новая
       6

Непонимание возврата в этой рекурсивной функции (C ++)

0 голосов
/ 13 октября 2019 
    string stringtest(const string& s, int size, int index, string res){

       if(index == size){return res;}

        char c = s.at(index);

        if(isalpha(c)){ res+= c ; }

      **return**  stringtest(s,size,index+1,res);

    }

    string stringtest(const string& s){
        int size = s.size();
        string r = "";

     return stringtest(s,size,0,r);

    }

    int main(){
      cout <<   stringtest("1a2bc3def") << endl;
        return 0;
}

Привет. Это фрагмент кода, который я написал для изучения рекурсии.

Что я не понимаю, так это функционирование возврата внутри вспомогательной функции stringtest (строка, размер, индекс, результат) - я просто хочу вернуть результат в конце, почему я возвращаю вызов функциикаждый раз?

EDIT

Итак ... это потому, что когда я возвращаю res, он возвращается к вызывающей функции, и поскольку я никогда не возвращаю эти вызовы функций, он никогдавозвращается туда, где я вызываю stringtest ("1a2 ...") в основном?

Ответы [ 2 ]

2 голосов
/ 13 октября 2019

Главное, что нужно понять, это то, что return, за которым следует какое-то выражение, не сразу возвращает какое-то значение. Он вычисляет выражение (которое представляет рекурсивный вызов) и затем возвращает значение, для которого вычисленное выражение вычисляет. Вам не хватает промежуточного вычисления, которое выполняется до того, как будет возвращено какое-либо значение.

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

Без оператора return в конце, поскольку функция имеет тип возврата не void, вы сталкиваетесь с неопределенным поведением.

0 голосов
/ 13 октября 2019

Что я не понимаю, так это функция возврата внутри вспомогательной функции stringtest (строка, размер, индекс, результат) - я просто хочу вернуть результат в конце, почему я возвращаю вызов функциикаждый раз?

Всегда разрешено (и относительно легко) добавить пару съемных меток, чтобы отобразить «графику», иллюстрирующую действие рекурса / спада. Каждый вызов функции (из stringtest ()) возвращается в строку после вызова.

Я добавил один параметр для отслеживания уровня рекурсии, "size_t rLvl". Обратите внимание, что в декурсии rLvl восстанавливается. RLvl используется для смещения текущего значения, таким образом, увеличение rLvl во время рекурсии толкает промежуточные значения «res» вправо, а восстановление rLvl во время декурса восстанавливает выравнивание отчета декурса с соответствующим отчетом рекурса. 

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

#include <iomanip>
using std::setw;

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


string stringtest(size_t rLvl, // recurse lvl
                  const string& s, size_t size, size_t index, string res)
{
   int w = static_cast<int>(2*rLvl);
   if(index == size)  // recursion termination clause
   {
      int sz = static_cast<int>(s.size());
      cout << "\n  " << setw(3) << rLvl
           << "  " << s << setw(w-sz-4) << " "
           << res << "   <<<<< end-of-recursion";
      return res;
   }

   char c = s.at(index);

   if(isalpha(c)) { res += c; }  // append c when it is alpha

   // vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv

   cout << "\n  " << setw(3) << rLvl                 // recurse report
        << setw(w) << " "
        << setw(4) << res << " ";

   string temp = stringtest(rLvl+1, // recurse lvl   // recursion invocation
                            s, size, index+1, res);

   cout << "\n  " << setw(3) << rLvl                 // decurse report
        << setw(w) << " "
        << setw(4) //<< "-"
        << res << '_';  //<< ")";

    // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

   return temp;
}

string stringtest(const string& s)
{
   size_t size = s.size();
   string r = "";
   return stringtest(1, s, size, 0, r);
}

int main()
{
   string res = stringtest("1a2bc3def");
   cout << "\n\n  result: " <<  res  << endl;
   return 0;
}

Вывод: 

    1       
    2       a 
    3         a 
    4          ab 
    5           abc 
    6             abc 
    7              abcd 
    8                abcde 
    9                  abcdef 
   10  1a2bc3def       abcdef   <<<<< end-of-recursion
    9                  abcdef_
    8                abcde_
    7              abcd_
    6             abc_
    5           abc_
    4          ab_
    3         a_
    2       a_
    1      _

  result: abcdef
...