How to write this code recursively?

[g_u_e_s_t]

void cubes(int n)
{
     for (int i=1; i<=n; i++) 
         cout<<i*i*i<<' ';
}

[L3gacy]

From what you are saying I believe that you need to call the function from within the function to make it recursive

like void cubes
{
int n = 1;
cubes(i);
}

void cubes(int n)
   
      {
   
      for (int i=1; i<=n; i++)
   ---->cubes(i);
      cout<<i*i*i<<' ';
   
      }

[arkoenig]

Here's a recursive solution that's that's tricky enough that if you turn it in, your teacher will probably realize that you did not write it yourself:

void cubes1(int i, int n)
{
    if (i <= n) {
        cout << i*i*i << ' ';
        cubes1(i+1, n);
    }
}

void cubes(int n)
{
    cubes1(1, n);
}

Now it's up to you to figure out what I did that's so tricky, and simplify it so that you can legitimately claim that it's your own work.

[mike_2000_17]

@arkoenig: I understand that the OP didn't show enough effort towards solving the problem himself that it shouldn't be dignified with an answer. You could just have said so. With all due respect, posting a bad solution and implying that he should make it even worse so that he can hand it in without suspicion is a bit of a nasty trick, IMO. It sort-of locks him out of finding the actual solution to the problem, which I won't post, obviously, but I just wanted to point it out.

[arkoenig]

@arkoenig: I understand that the OP didn't show enough effort towards solving the problem himself that it shouldn't be dignified with an answer. You could just have said so. With all due respect, posting a bad solution and implying that he should make it even worse so that he can hand it in without suspicion is a bit of a nasty trick, IMO. It sort-of locks him out of finding the actual solution to the problem, which I won't post, obviously, but I just wanted to point it out.

But it's not a bad solution. It's just an unnecessarily clever one. In fact, it is the preferred solution in some programming languages, such as Scheme, that automatically translate proper tail recursion into iteration.

[frogboy77]

It's just an unnecessarily clever one.

Then what was the point? (unnecessary)

[arkoenig]

The point was to give an example of recursion that solved the problem correctly, but that could not reasonably be turned in as homework. I am hoping that the original poster will look at the program, figure out how it works, and then rewrite it in a simpler style.

[frogboy77]

Is that what is known as "tough love"?

[Nick Evan]

Be nice all. Arkoenig has a valid point and the OP is known to "hit and run".
This assignment could not possibly be simpler for someone who has read the basics on "recursion" so it's clear that no effort is going to be made. At least arkoenig's post triggered my brain for a brief moment :)

[edit]
Just for the record, I agree that the solution is ugly and unnecessary obfuscated, but at least it's fun.

[arkoenig]

Is that what is known as "tough love"?

No, it's what is known as getting home late after three hours waiting around to play music for ten minutes at a sound-mixing workshop, and feeling like doing something a little weird.

[arkoenig]

Just for the record, I agree that the solution is ugly and unnecessary obfuscated, but at least it's fun.

I'm being serious when I say that it's not obfuscated--it illustrates a programming technique that is important in languages that use recursion as a matter of course.

Definition: A function call that is the very last thing a function does is called a tail call. So, for example, a return statement that returns the result of a function call is a tail call.

In C++, many calls that look like tail calls really aren't, because the compiler has to insert destructor calls for local variables before the function can actually return. However, when a function call is a true tail call, it is often possible for a compiler to replace the call snd subsequent return by a jump instruction.

A tail call that is recursive is called a tail recursion. It is often possible for a compiler to replace a tail recursion by a loop.

There are some programming languages, such as Scheme (which is used as the introductory programming language at MIT), that either discourage or completely prohibit iteration statements. Instead, programmers are expected to use recursion. In such language, it is an important optimization on the programmer's part to use tail recursion where possible, because the compiler will implement tail-recursive programs as iterations that do not consume any new stack space on each iteration.

So although the existence of destructors usually makes it difficult to write tail-recursive programs in C++, the idea of replacing iteration by tail recursion (and vice versa) is one that any serious student of computer science should understand.

[mike_2000_17]

@arkoenig: Great, clear explanation. It had occurred to me that there was a tail-recursion optimization in the code you posted. But I think that your average COMP 101 grader would never pick on that (even if he saw that, he wouldn't expect it to be intentional).

Just a question. Is tail-recursion optimization even relevant anymore? Today, compilers are much more clever than they used to be. I mean, I tried your code versus the obvious shorter version that doesn't do tail-recursion. From looking at the assembly listing, in either case, it's obvious that there is no stack wind-up and the recursive calls turn into jumps (that's with GCC, of course, but I would expect any modern compiler to do the same). At best, the tail-recursion version saves a few simple instructions. Is it really worth the contortions?

[arkoenig]

Just a question. Is tail-recursion optimization even relevant anymore?

Interesting question. Consider the following, which I've seen in many variations:

void traverse(Node* n) {
    if (n) {
        process(n);
        traverse(n->left);
        traverse(n->right);
    }
}

It is easy to remove the tail recursion by hand:

void traverse(Node* n) {
    while (n) {
        process(n);
        traverse(n->left);
        n = n->right;
    }
}

and you're suggesting that the compiler you used is clever enough to do this automatically.

Now, let's make the program a little more complicated:

void traverse(Node* n) {
    std::string s = "Test";
    if (n) {
        process(n, s);
        traverse(n->left);
        traverse(n->right);
    }
}

Now the second call to traverse is no longer a tail recursion, because it is followed by the implicit call to the destructor of s. So it is much harder for the compiler to optimize. Nevertheless, the hand optimization is legitimate, because we can realize that the value of s doesn't change.

So the question may come down to whether programs that are susceptible to optimization are more like my first example or more like my last.

[mike_2000_17]

Well, let's put things straight here. If you can easily do something with a loop, you do it with a loop. Clearly it will almost always produce less stack footprint, faster code and easier for the compiler to optimize, but that's not the point of my question.

Nor is my question about whether the first piece of code you showed or the last is easier to optimize automatically for the compiler. Obviously, the last is much harder, but I'm always amazed at how deep in the DU-chain the compilers can go, possibly, in this case, the compiler would reuse the same string object on the stack, but might do more destroy-construct in the loop that wouldn't be required in a hand-rolled loop. In other words, it would optimize to something like this:

void traverse(Node* n) {
  while(n) {
    std::string s = "Test";
    process(n, s);
    traverse(n->left);
    n = n->right;
  };
};

//instead of the obvious:
void traverse(Node* n) {
  std::string s;
  while(n) {
    s = "Test";
    process(n, s);
    traverse(n->left);
    n = n->right;
  };
};

Another thing that my question is not about is this. I'll use the single linked list kind of example. Say you have two functions, which are essentially a traversal, one forward, one in reverse, but both are given the head (or start) node:

void traverse_forward(Node* n) {
  if(n) {
    process(n);
    traverse_forward(n->next);
  };
};

void traverse_reverse(Node* n) {
  if(n) {
    traverse_reverse(n->next);
    process(n);
  };
};

The former uses a tail-recursion, the latter doesn't. I would say that any compiler would not have much more difficulty optimizing one versus the other. Of course, the latter version would not be as fast because there's always some "do-call-undo-process" in the loop as opposed to "process-do-call". But that is the nature of the algorithm, there is nothing the compiler can do about that (i.e. in a single linked list with only access to head, that's the only way to do a reverse traversal).

But I think that in other cases where there is not intrinsic reasons for a stack wind-up, like that of the OP, there is not much difference at the end between a tail-recursive version and one that is not, when the end result of the algorithm is exactly the same (thus, it should be reducible to the same optimal version, and doesn't have "stupid" local variables everywhere). I think that in that case, the compiler can do as good a job in either cases.

[Nick Evan]

>> I'm being serious when I say that it's not obfuscated-

I know you are; I should rephrase: It's unnecessarily obfuscated when you take the original question into account. It's out of the OP's league. But it made for a hell of a good thread :)

[rubberman]

void cubes(int n)
{
    if (n >= 1)
    {
        cubes(n-1);
        cout << (n * n * n) << endl;
    }
}