Transform iterative function to recursive function

Question

I was having a discussion with a coworker about how to transform the following iterative function into a strictly recursive function. We know that all iterative functions can be transformed into recursive functions; however, my coworker remembered that this particular implementation used only three parameters. We can't re-solve this problem. Are we remembering incorrectly? Or are we missing something simple?

void iterative_function (char a, char b, int width) {
  int i = width;
  while (i > 0) {
    cout << string(i, a) << string(width-i, b) << endl;
    i -= 2;
  }
  i = width % 2;
  while (i <= width) {
    cout << string(i, a) << string(width-i, b) << endl;
    i += 2;
  }
}

Where the output looks something like below when called like iterative_function('X', '-', 5).

XXXXX
XXX--
X----
XXX--
XXXXX

EDIT: Here is a small skeleton of what the recursive version might look like:

void recursive_function (char a, char b, int width) {
  if (width > -1) {
    cout << string(width, a) << endl;
    recursive(a, b, width - 2);
    cout << string(width, a) << endl;
  }
}

Except the problem here is filling the right side out with, say, hyphens.

Low hanging fruit: Use two recursive functions and use the stack to replace the role i is playing. — BlamKiwi
– BlamKiwi, Commented Feb 10, 2015 at 7:17
How are you going to keep track of the total width? It's easy to solve if you only have to print one side of the function, but more difficult when you need to fill the other side with hyphens in this example. — lswim
– lswim, Commented Feb 10, 2015 at 7:24
@tekknolagi try build a state machine to match valid output strings in the general case. I'm pretty sure you need something more general than a push down automata which is why you're having issues doing a simple transformation. — BlamKiwi
– BlamKiwi, Commented Feb 10, 2015 at 10:38

Lrrr · Accepted Answer · 2015-02-10 07:49:45Z

1

Here is the recursive function, I just add another len to your function you can see in here, that its output is exactly like the output of your code here.

#include <iostream>
using namespace std;

void i_f(char a, char b, int width,int len) {

  if(len <0 || width < 0)
    return;
  cout <<string(width, a) << string(len, b) << endl;
  i_f(a,b,width-2,len+2);
  cout <<string(width, a) << string(len, b) << endl;
}

int main() {
    i_f('X', '-', 5,0);
    return 0;
}

your code output:

XXXXX
XXX--
X----
X----
XXX--
XXXXX

my code output:

XXXXX
XXX--
X----
X----
XXX--
XXXXX

P.S After I posted my answer I saw your edit, although you edited your question 10 minutes before my answer, and I can see that you choose a path like my answer yourself.

edited Feb 10, 2015 at 7:49

answered Feb 10, 2015 at 7:44

Lrrr

4,8055 gold badges44 silver badges65 bronze badges

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

11 Comments

tekknolagi Over a year ago

The idea, though, is to get the function to work with the same amount of parameters. It's trivial if we add another.

Lrrr Over a year ago

@tekknolagi just give me some time, I'll edit my answer to what you want.

tekknolagi Over a year ago

Take all the time you like! No worries.

Lrrr Over a year ago

@tekknolagi in the mean time, edit your question, the output is wrong in your question :D

Marichyasana Over a year ago

Original program output 5 rows, your answer program outputs 6; but was a change made to the original? How many rows are desired?

|

Collectives™ on Stack Overflow

Transform iterative function to recursive function

1 Answer 1

11 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

11 Comments

Your Answer

Sign up or log in

Post as a guest

Related