Optimise a recursive function

Question

For n = 18 my code takes more than 0.5s on a 1GHz machine. I think this is due to the fact that I am using a recursive function, yet I don't really knwo how to optimise this code because it actually just "prints" numbers... Hence maybe the problem comes from the fact that I am using recursive function.

Here is my code :

#include<iostream>

void singleSquareRemove (int s)
{
  if (s == 1)
    {
      std::cout << 1 << std::endl;
      return;
    }
  else
    {
      for (int i = s-1; i >=1; --i)
    singleSquareRemove(i);
      std::cout << s << std::endl;
    }
}
void whenSquareisFull (int v)
{
  if (v == 1)
    {
      std::cout << 1 << std::endl;
      return;
    }
  else if (v == 2)
    {
      std::cout << 2 << std::endl;
      return;
    }
  else if (v == 3)
    {
      std::cout << 1 << std::endl;
      std::cout << 3 << std::endl;
      return;
    }
  else
    {
      whenSquareisFull(v-2);
      for (int i = v-3; i > 0; --i)
    singleSquareRemove(i);
      std::cout << v << std::endl;
    }
}
int main()
{

  unsigned int n {0};
  std::cin >> n;

  whenSquareisFull(n);
  for (int i = n-1; i > 0; --i)
    {
      singleSquareRemove(i);
      }

}

Normally you have to benchmark and such, but `std::endl` probably steals a lot of time. — Rakete1111, Oct 17 '17 at 19:51
I think it might help if you made the recursive call a tail call so that it could be optimized by the compiler. — Fred Larson, Oct 17 '17 at 19:52
I am willing to bet some money (not much though) that you are compiling in debug, no optimizations enabled. — bolov, Oct 17 '17 at 19:53
@Rakete1111 There's really a different time execution between '\n' and std::endl ? — Salutsalut1, Oct 17 '17 at 19:56
@FredLarson It seems more clear to me, and I don't really know how to implement this using recursion... — Salutsalut1, Oct 17 '17 at 19:57
That does seem exceptionally slow, are you sure it is not the fault of whatever you're trying to write to? — George, Oct 17 '17 at 19:58
@Salutsalut1 printing is buffered, `endl` will flush the buffer. Always ending with `endl` will stop your buffering from working effectively. — Fantastic Mr Fox, Oct 17 '17 at 19:58
@Salutsalut1 jup, see this https://stackoverflow.com/q/213907/3980929 — Rakete1111, Oct 17 '17 at 19:58
Thank you very much for all your answers and my problem is actually solved because using std::endl for n = 17 takes 0.5 s while using '\n' it takes only 0.03. Next time i'll be carefull on using std::endl; — Salutsalut1, Oct 17 '17 at 20:04

score 0 · Accepted Answer · answered Oct 17 '17 at 20:22

The time sink is when you are printing the value and flushing the output (std::endl).

You could avoid that time sink by using a type of "buffer", like a std::vector that you could then iterate over to print. In this way, the time is spent on the actual "calculations", which you can then profile, versus spending time on printing the output.

Example using your code:

#include <iostream>
#include <vector>

static std::vector<int> values;

void singleSquareRemove (int s)
{
    for (int i = s - 1; i >= 1; --i)
        singleSquareRemove(i);
    values.push_back(s);
}

void whenSquareisFull (int v)
{
    switch (v) {
        case 1: case 2:
            values.push_back(v);
        break;
        case 3: {
            values.push_back(1);
            values.push_back(v);
        } break;
        default: {
            whenSquareisFull(v - 2);
            for (int i = v - 3; i > 0; --i) singleSquareRemove(i);
            values.push_back(v);
        } break;
    }
}

int main()
{
    unsigned int n {0};
    std::cin >> n;
    // start timing here
    whenSquareisFull(n);
    while (--n > 0) singleSquareRemove(n);
    // stop timing here
    for (auto itr = values.begin(); itr != values.end(); ++itr)
        std::cout << *itr << std::endl;
    return 0;
}

Hope that helps!

Optimise a recursive function

1 Answers1