How can I convert a basic nested loop to recursive in C++

Question

I'm learning recursion and I am looking for a simple example of how to convert this basic nested loop to a recursive function. Thanks for your input: EDIT: I provided my failed attempt to convert the nested loop. I can't yet envision the recursive process, but my research has shown this is the recursive format. It will not display output ,as I'm not sure where to place the cout line.

The Nested loop:

#include "stdafx.h"
#include<string>
#include<fstream>
#include<iomanip>
#include<vector>
#include<iostream>
#include<string.h>


using namespace std;

void recursive(int x, int y)
{
    for (int i = x; i > 0; i--)
        for (int j = y; j > 0; j--)
        {
            cout << i << " , " << j << endl;
        }
}
int main()
{
    int x, y;
    cout << "Enter 2 numbers:\n";
    cin >> x >> y;
    recursive(x, y);
    return 0;
}

My attempt to convert to a recursive function:

void recursive(int start, int N)
{

    for (int x = start; x < N; x++)
    {

        recursive(x + 1, N);

    }



    for (int y = start; y < N; y++)
    {

        recursive(y + 1, N);

    }
}

int Main()
{
    recursive(0,3);
    return 0;
}

Ah ! We've a problem there pal ! SO doesn't work that way. Try to come up with a code for recursion and then ask for suggestions to improve/correct it. — sjsam
– sjsam, Commented Nov 26, 2017 at 21:31
I have been working on converting this for two days, and I assure you this is not laziness. I just have trouble envisioning what the recursive functions are doing to the data. I have tried drawing the stack calls, and looking at various solutions. I think converting this simple recursion will help me envision it. — MGT
– MGT, Commented Nov 26, 2017 at 22:12
Kudos and +1 for 'stub' function. In one simple stub you have provided the name you want, the parameters you want (input), and some (iterative) code to describe the result (output). — 2785528
– 2785528, Commented Dec 10, 2017 at 20:50

Cirrus · Accepted Answer · 2017-11-26 22:31:27Z

2

void recursive(int x, int y, int temp)
{
  if(x > 0) {
    if(y > 0) {
      cout << x << " " << y << endl;
      recursive(x,y-1,temp);
    }
    else {
      y = temp;
      recursive(x-1,y,temp);
    }
  }
}

The best solution I've came so far, yet it requires additonal variable just to let y go back to it's oryginal value. You have to call it by recursive(x,y,y);

answered Nov 26, 2017 at 22:31

Cirrus

767 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

MGT Over a year ago

Yes, its an elegant and simple solution, and I neglected the fact that a 'start' variable was needed. best regrds.

rcgldr · Accepted Answer · 2017-11-26 23:27:15Z

2

If multiple recursive functions are allowed, use one for each loop level. This limits recursive depth to x+y instances instead of x*y instances.

#include <iostream>

using namespace std;

// inner loop    
void recursivey(int x, int y)
{
    if(y <= 0)
        return;
    cout << x << " , " << y << endl;
    recursivey(x, y-1);
}

// outer loop    
void recursivex(int x, int y)
{
    if(x <= 0)
        return;
    recursivey(x, y);
    recursivex(x-1, y);
}

int main()
{
    int x, y;
    cout << "Enter 2 numbers:\n";
    cin >> x >> y;
    recursivex(x, y);
    return 0;
}

edited Nov 26, 2017 at 23:27

answered Nov 26, 2017 at 23:22

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

1 Comment

Stef Over a year ago

"This limits recursive depth to x+y instances instead of x*y instances." Technically true, but if tail-recursion optimisation is on, that doesn't make much of a difference.

travisjayday · Accepted Answer · 2017-12-02 14:36:18Z

1

Correct me if I'm wrong but I think this is the "simplest" way to pack it all into one recursive function... It's pretty ugly (and nested for-loops are far better & easier) but if you really want recursion, this will get the job done.

I came up with this by thinking about what the nested for loop does-- it iterates y times, decrements x, resets y to its original value, then iterates y times, decrements x, resets y ....... until x == 0. This recursive function uses a similar mindset, in that it calls itself, decrementing y each time, and once y == 1, it decrements x, and resets y (with start_y). Once x == 1 it returns true, and all callers then also return true until it lands back in main().

Read through the comments in the code and see if you get it. I'm not very proud of it but making a nested loop with a recursive function just ins't very pretty. That's why nested loops exist...

void recursive(int x, int y, int start_y)
{
    cout << x << " , " << y << endl; 

    // calls itself until y = 1, then goes on to if(x>1), decrementing x
    if (y > 1)                              
    {
            recursive(x, --y, start_y);
            return;
    }

    // calls itself and sets y = starting value of y (the userinput) 
    // this has the same effect as completing the inner for loop, then 
    // re-running it with --x
    if (x > 1)
    {
        recursive(--x, start_y, start_y);  // resets y value to start_y. if this is true, it's a signal that the function is done, so return true. 
        return;
    }
}


int main()
{
    int x, y;
    cout << "Enter 2 numbers:\n";
    cin >> x >> y;

    // inner loop -- I recommend this method... :-)
    for_loop(x, y);

    cout << endl; 

    // using recursion -- I don't recommend this method... :-(
    recursive(x, y, y); 

    return 0;
}

edited Dec 2, 2017 at 14:36

answered Nov 26, 2017 at 22:22

travisjayday

8247 silver badges18 bronze badges

2 Comments

MGT Over a year ago

I agree with you that a nested loop is better and easier. But the purpose of converting it to recursion was so that I could get better and using it. Your solution works great. best regards.

travisjayday Over a year ago

@DOUGLASO.MOEN, thanks for that - I don't know what I was thinking :-). I fixed it such that it only returns nothing now.

myworldbox · Accepted Answer · 2022-03-14 00:53:53Z

1

Quick answer:

// int arr[] = {3, 3, 3};
// n_for_loop(0, 3, arr);

void n_for_loop(int x, int size, int arr[])
{
    static int* arrTemp(new int[size]);
    if (x >= size)
    {
        for (int i = 0; i < size; i++)
        {
            cout << arrTemp[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = 0; i < arr[x]; i++)
    {
        arrTemp[x] = i;
        n_for_loop(x + 1, size, arr);
    }
}

edited Mar 14, 2022 at 0:53

answered Jan 24, 2022 at 7:01

myworldbox

4211 gold badge8 silver badges13 bronze badges

Comments

2785528 · Accepted Answer · 2017-12-10 20:56:19Z

I am looking for a simple example of how to convert this basic nested loop to a recursive function

'simple' examples, sure. (why not?)

I think all 3 previously submitted contributions work ok. I believe I have compiled and run each of them on my system.

Kudos to rcgldr - That submittal stands out for achieving tail-recursion. (I did not confirm this issue on the others.)

Magic Numbers:

for-loops have 3 'Parameters': start, stop, and stride

 for (int v = start; v < stop; v += stride)

Because for-loops have a rigid layout, magic numbers are tolerated, and perhaps desired. IMHO, your use of 2 magic numbers (0 and -1) is fine.

In code with a more flexible layout (other loops types, recursion, etc), such magic numbers should be discouraged.

Testability:

the vertical format of your stub 'report' does not lend itself to easy human inspection / comparison. Consider a 'horizontal output' display (one alternative is presented.)
any text output needs to be suppressed during performance measurements. (one technique is presented)

C-style vs C++ style

So far, only C-style functions have been submitted.
If your C++ code has no class, why bother?

My environment

Ubuntu 15.10, g++-5, GNU Emacs 26, performance measurements use -O3 (debugging uses -O0)
My build options:

g++-5 -m64 -O3 -ggdb -std=c++14 -Wall -Wextra -Wshadow -Wnon-virtual-dtor -pedantic -Wcast-align -Wcast-qual -Wconversion -Wpointer-arith --Wunused Woverloaded-virtual -O3 dumy542.cc -o dumy542

Code File name "dumy542.cc"

Summary

In the submitted code, the performance of the 2 recursive forms are the same as the iterative form. (tail recursion)
I have confirmed tail recursion - both recursive codes run 'deep' with no stack overflow. The Ubuntu 15.10 default 'stack' size is 8 Mbytes. Demo uses 12 Million recurse depth. When code is built with -O0, the code stack overflows. (SO) When -O3, no SO.

Demo's of interest

The presence of any 3rd cmd-line-param (i.e. 'm') enables text output

./dumy542 3 15 m - runs 3 x 15, reports duration, and 3 lines text output

./dumy542 3 60 m - fits on my full screen

Note - an attempt to enable test output with 'large' output will trigger an assert, for your recovery convenience. (You may remove it)

With only 1 or 2 cmd line params, text output is suppressed

./dumy542 3 12345678 - runs each test 3x of 12+ Million

The first section of code presents the iterative code, and 2 tail-recursive code examples. All are based on submitted code, to which I have refactored to use ssDiag (to support suppressing text output) and a more 'horizontal' display technique.

Note - an assert has been added (to these examples) to prevent compiler from optimizing code away.

The test wrappings (with C++ chrono timing measurements) are below.

#include <chrono>
// 'compressed' chrono access --------------vvvvvvv
typedef std::chrono::high_resolution_clock  HRClk_t; // std-chrono-hi-res-clk
typedef HRClk_t::time_point                 Time_t;  // std-chrono-hi-res-clk-time-point
typedef std::chrono::nanoseconds            NS_t;    // std-chrono-nanoseconds
using   namespace std::chrono_literals;      // support suffixes like 100ms, 2s, 30us

#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <cassert>

uint64_t Kount = 1; // diagnostic only


// C style C++ function by MGT
// refactored (by DMoen) to use ssDiag and 'horizontal' display
void iterate_MGT(int x, int y, std::stringstream* ssDiag )
{
   for (int i = x; i > 0; i--) // magic numbers xStop (0) & xStride (-1)
   {
      if(nullptr != ssDiag) { (*ssDiag) << "\n  i=" << i << ": "; }
      else { assert(++Kount); } // with side-effects

      for (int j = y; j > 0; j--) // magic numbers yStop (0) & yStride (-1)
      {
         if(nullptr != ssDiag) { (*ssDiag) << j << "  "; }
         else { assert(++Kount); }  // with side-effects
      }
   }
}


// C style C++ function(s) by 'rcgldr'
// refactored (by DMoen) to use ssDiag and 'horizontal' display
void recurseY(int x, int y, std::stringstream* ssDiag)
{
   if(y <= 0) return; // magic number yStop (0)

   if(nullptr != ssDiag) { (*ssDiag) << y << "  " ; }
   else                  { assert(++Kount);    }  // with side-effects

   recurseY(x, y-1, ssDiag);  // magic number y-stride (-1)
}

void recurseX(int x, int y, std::stringstream* ssDiag)
{
   if(x <= 0) return; // magic number xStop (0)

   if(nullptr != ssDiag) { (*ssDiag) << "\n  i=" << x << ":  " ; }
   else                  { assert(++Kount);    }  // with side-effects

   recurseY (x,   y, ssDiag);
   recurseX (x-1, y, ssDiag); // magic number x-stride (-1)
}



// C++ class - created from tail recursive code (submitted by 'rcgldr')
//  by DMoen to use ssDiag and 'horizontal' display
class Recursive_t
{
public:
   static void recurse (int x, int y, std::stringstream* ssDiag)
      {
         Recursive_t rcgldr(x, y, ssDiag); // ctor
         rcgldr.recurseX();                // go
      }                                    // dtor on exit

private:
   int                m_x;
   int                m_y;
   int                m_yStart;
   std::stringstream* m_ssDiag;

   enum Constraints : int  // no need for magic numbers
   {
      xStop = 0, xStride = -1,
      yStop = 0, yStride = -1,
      ConstraintsEnd
   };

   Recursive_t () = delete;  // disallow default ctor

   Recursive_t (int xStart, int yStart, std::stringstream* ssDiag)
      : m_x      (xStart)
      , m_y      (yStart)
      , m_yStart (yStart)
      , m_ssDiag (ssDiag)
      {
      }

   void recurseX() // outer loop
      {
         if(m_x <= xStop)  return;

         if(nullptr != m_ssDiag) { (*m_ssDiag) << "\n  i=" << m_x << ":  " ; }
         else                    { assert(++Kount); } // with side-effects

         recurseY();
         m_x += xStride;
         recurseX();
      }

   void recurseY()  // inner loop
      {
         if(m_y <= yStop) { m_y = m_yStart; return; }

         if(nullptr != m_ssDiag) { (*m_ssDiag) << m_y << "  " ; }
         else                    { assert(++Kount); } // with side-effects

         m_y += yStride;
         recurseY();
      }

}; // class Recursive_t

The test code and main:

class T542_t
{
   int               m_xStart;
   int               m_yStart;

   std::string        m_rslt;
   std::stringstream* m_ssRslt;

   std::string        m_diag;
   std::stringstream* m_ssDiag;

   const uint         m_capacity;

public:


   T542_t()
      : m_xStart(0)
      , m_yStart(0)
        //
        // m_rslt - default std::string ctor ok
      , m_ssRslt (nullptr)
        // m_diag - default std::string ctor ok
      , m_ssDiag (nullptr)
      , m_capacity (1000)
      {
         m_rslt.reserve(m_capacity);
         m_ssRslt = new std::stringstream(m_rslt); // always
         //
         m_diag.reserve(m_capacity);
         // m_ssDiag only when needed

         resetTest();

         m_rslt.clear();
         assert(m_rslt.capacity() == m_capacity);
         assert(m_rslt.empty());
         assert(m_rslt.size() == 0);
      }

   ~T542_t() = default;


   int exec (int argc, char* argv[])
      {
         switch (argc)
         {

         case 2: // one parameter
         {
            m_xStart = std::stoi(std::string(argv[1]));
            m_yStart = m_xStart;
            return (test("\n  one command line parameter 'N':  duration rslts only"));   // NOTE 1
         }
         break;

         case 3: // two parameters
         {
            m_xStart = std::stoi(std::string(argv[1]));
            m_yStart = std::stoi(std::string(argv[2]));
            return (test("\n  two command line parameters, X & Y: duration rslts only"));   // NOTE 1
         } break;

         case 4: // three parameters
         {
            m_xStart = std::stoi(std::string(argv[1]));
            m_yStart = std::stoi(std::string(argv[2]));

            m_diag.clear();
            assert(m_diag.capacity() == m_capacity);

            m_ssDiag = new std::stringstream(m_diag);

            return (test("\n  three command line parameters, X & Y: duration + intermediate results"));   // NOTE 1
         } break;

         case   1:
         default :
         {
            std::cerr
               << "\n  Usage: "
               << "   argc (" << (argc-1) << ") not expected, use 1, 2, or 3 cmd line parameters.\n"
               //
               << "\n     2  (one parameter)    : test with NxN, show duration only\n"
               << "\n     3  (two parameters)   : test with MxN, show duration only\n"
               //
               << "\n     5  (three parameters) : test with MxN, show intermediate results\n"
               //
               << "\n   other                   : Usage\n"
               << std::endl;
            return 0;
         }

         } // switch

         assert(m_xStart);
         assert(m_yStart);


      } // exec (int argc, char* argv[])

private:

   int test(std::string note)
      {
         int64_t a_lim = m_xStart * m_yStart;
         assert(a_lim > 0); // wrap around possible: example:  3 x 1234567890
         std::cout << note << ",  Using  " << m_xStart << " & " << m_yStart
                   << "  (" << digiComma(std::to_string(a_lim))
                   << ")\n" << std::endl;

         if(nullptr != m_ssDiag) { // when displaying output, make sure
            assert (m_yStart <= 80);                // short line and small total
            assert((m_xStart * m_yStart) <= 2000);
         }

         if(true) // for consistent start up - ubuntu app 'load' delay? cache flush?
         {
            assert(nullptr != m_ssRslt);
            (*m_ssRslt) << "\n  \n  ::xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ";
            testRecurse2  (); testRecurse1  (); testIterate ();
            resetTest(); // discard results
         }

         testIterate (); showTest();  resetTest();
         testRecurse1 ();  showTest();  resetTest();
         testRecurse2 ();  showTest();  resetTest();

         return 0;
      } // int test()


   void showTest()
      {
         std::cout << m_ssRslt->str() << std::endl;
         if(nullptr != m_ssDiag)
            std::cout << m_ssDiag->str() << std::endl;
      }


   void testIterate()  // C style C++ function, submitted by MGT, iterative function
      {
         assert(nullptr != m_ssRslt);
         (*m_ssRslt) << "\n  (C style C++ function)\n  ::iterate_MGT (int, int, ss&)             ";

         Time_t start = HRClk_t::now();

           ::iterate_MGT (m_xStart, m_yStart, m_ssDiag); // invoke the C++ function
         //^^ --- file scope

         auto  duration_ns = std::chrono::duration_cast<NS_t>(HRClk_t::now() - start);
         (*m_ssRslt) << "    duration:  " << std::setw(10)
                     << digiComma(std::to_string(duration_ns.count())) << " ns ";
      } // testIterate()



   void testRecurse1 () // C style C++ function, submitted by rcgldr, tail-recursive
      {
         assert(nullptr != m_ssRslt);
         (*m_ssRslt) << "\n  (C style C++ function)\n  ::recurseX (int, int, ss&)                 ";

         Time_t start = HRClk_t::now();

           ::recurseX(m_xStart, m_yStart, m_ssDiag);
         //^^ --- file scope

         auto  duration_ns = std::chrono::duration_cast<NS_t>(HRClk_t::now() - start);
         (*m_ssRslt) << "   duration:  " << std::setw(10)
                     << digiComma(std::to_string(duration_ns.count())) << " ns ";
      } // void testRecurse1 ()



   void testRecurse2 () // C++ class, tail-recursive, method
      {
         assert(nullptr != m_ssRslt);
         (*m_ssRslt) << "\n  (C++ class method)\n    Recursive_t::recurse (int, int, ss&)     ";

         Time_t start = HRClk_t::now();

           Recursive_t::recurse(m_xStart, m_yStart, m_ssDiag);
           //^^^^^^^^^ class scope

         auto  duration_ns = std::chrono::duration_cast<NS_t>(HRClk_t::now() - start);
         (*m_ssRslt) << "   duration:  " << std::setw(10)
                     << digiComma(std::to_string(duration_ns.count())) << " ns ";
      } // void testRecurse2 ()



   void resetTest() { resetRslt(); resetDiag(); Kount = 1; }

   void resetRslt() { m_rslt.clear(); // clear bufer
      if (nullptr != m_ssRslt) { m_ssRslt->str(m_rslt); m_ssRslt->clear(); } }

   void resetDiag() { m_diag.clear(); // clear buffer
      if (nullptr != m_ssDiag) { m_ssDiag->str(m_diag); m_ssDiag->clear(); } }


   // convenience - insert comma's into big numbers for readability
   std::string digiComma(std::string s)
      {  //vvvvv--sSize must be signed int of sufficient size
         int32_t sSize = static_cast<int32_t>(s.size());
         if (sSize > 3)
            for (int32_t indx = (sSize - 3); indx > 0; indx -= 3)
               s.insert(static_cast<size_t>(indx), 1, ',');
         return(s);
      }

}; // class T542_t

int main(int argc, char* argv[])
{
   T542_t  t542;
   return  t542.exec(argc, argv);
}

Example results

command line: ./dumy542 3 15 m

three command line parameters, X & Y: duration + intermediate results, Using 3 & 15 (45)

(C style C++ function) ::iterate_MGT (int, int, ss&) duration: 6,319 ns

i=3: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
i=2: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
i=1: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

(C style C++ function) ::recurseX (int, int, ss&) duration: 6,639 ns

i=3: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
i=2: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
i=1: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

(C++ class method) Recursive_t::recurse (int, int, ss&) duration: 6,480 ns

i=3: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
i=2: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
i=1: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

command line: ./dumy542 3 12345678

two command line parameters, X & Y: duration rslts only, Using 3 & 12345678 (37,037,034)

(C style C++ function) ::iterate_MGT (int, int, ss&) duration: 46,369,155 ns

(C style C++ function) ::recurseX (int, int, ss) duration: 44,099,411 ns

(C++ class method) Recursive_t::recurse (int, int, ss&) duration: 42,898,124 ns

Duration notes

multiple runs have different results, often changing which function appears faster. This particular result show both recursions faster than iteration.

On duration -- imagine capturing 1000+ durations into a vector, and sorting them. Instead of averaging the results, we simply report the fastest time of each, because the smallest duration can not get any smaller. I have completed this effort ... with very stable and repeatable measurements. "fastest durations (strength): iterate: 4,272,835 (8) recurseX: 4,272,795 (2) recurse: 4,272,795 (4)." i.e. The fastest times of each implementation. total run time 13 sec, 3 x 1234567 (3,703,701) increments, *1000+ runs.

myworldbox · Accepted Answer · 2022-01-24 04:52:31Z

-1

Quick answer:

void createTraining_2(int x, int y, int z) // 3d recursive for loop
{
    static int start_y = y;
    static int start_z = z;

    if (x < y && x != y && y != z && z != x)
    {
        // yourFunction();
    }

    if (z > 0)
    {
        createTraining_2(x, y, --z);
        return;
    }

    if (y > 0)
    {
        createTraining_2(x, --y, start_z);
        return;
    }

    if (x > 0)
    {
        createTraining_2(--x, start_y, start_z);
        return;
    }
}

answered Jan 24, 2022 at 4:52

myworldbox

4211 gold badge8 silver badges13 bronze badges

Collectives™ on Stack Overflow

How can I convert a basic nested loop to recursive in C++

6 Answers 6

1 Comment

1 Comment

2 Comments

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

1 Comment

1 Comment

2 Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related