Recursive Algorithm using characters

[sariki]

Hello,
I just have a question about Recursive algorithms using characters.

So If i was to use something like a $ or @ and I wanted to have this output a certain amount of times that I define. How would I declare the $ or @?

Thanks

[Duthomhas]

Both $ and @ are characters to display, so they should be '$' and '@'. If you wish them to be strings, you can do that as well: "$" and "@".

Are you sure your question isn't more about how to implement the recursion itself?


Remember, recursion is a way of writing a loop. If I wanted to print a $ five times, I could use a loop:

for (int n = 0; n < 5; n = n+1)
  cout << '$';

The important piece of information for running the loop is the variable n -- without it, the loop would not know when to stop.

Recursion works the same way: you need an additional piece of information to know when to stop. You can do this by making an argument to the function.

void print_5_dollar_signs( int n = 0 )  // Same as the loop: start with n = 0
{
  if (n == 5) return;  // The loop says, while n < 5 continue. Here we say, if !(n < 5), we quit.
  cout << '$';
  print_5_dollar_signs( n+1 );  // Same as the loop: next n = current n+1
}

At this point, you may notice that your function is not very general. What if I wanted to print 7 dollar signs?

We could just add another argument:

void print_x_dollar_signs( int x, int n = 0 )
{
  if (n == x) return;
  cout << '$';
  print_x_dollar_signs( x, n+1 );
}

That is not very satisfying, though, because it seems that we have too many arguments in there. You may have already seen the possibility in your own head: why not count backwards?

Instead of starting at zero and counting up to 5, why not start at 5 and count down to zero?

for (int n = 5; n > 0; n = n-1)
  cout << '$';

Now we only need one argument again:

void print_n_dollar_signs( int n = 5 )
{
  if (n == 0) return;
  cout << '$';
  print_n_dollar_signs( n-1 );
}

That's a whole lot prettier. And you can use it anywhere:

#include <iostream>
using namespace std;

void print_n_dollar_signs( int n )
{
  if (n == 0) return;
  cout << '$';
  print_n_dollar_signs( n-1 );
}

int main()
{
  print_n_dollar_signs( 5 );
  cout << endl;

  print_n_dollar_signs( 7 );
  cout << endl;
}

The next thing to think about is... what if I want to print something else?
(Hint: add an argument to the function!)

Hope this helps.

[sariki]

This has helped me tons! Thank I do appreciate that. I am pretty weak with Recursive Algorithms and I need to make sure that I understand them. Now if I passed it as a function say

void numsigns

I wanted to call this later I would just call the way that you did?

like:

int main()
{numsigns(5);
outf << endl;
}

One more thing. If I am using a output file to store the information would i declare this in int main? Like:

int main()
{
ofstream outf("data.ot");
numsigns(5);
outf << endl;
}

[Duthomhas]

Hopefully you have tried those two solutions to see what has happened.

In the first, it worked fine. In the second, though, whatever it is you are printing still went to the screen and not to the file.

That's because in the function you say cout << '$'. But you would rather outf << '$'.

One option is to pass the target stream as an argument to the function:

#include <fstream>
#include <iostream>

void numsigns( int n, ostream& outs )
{
  if (n == 0) return;
  outs << '$';
  numsigns( n-1, outs );
}

int main()
{
  // print five $ to file
  ofstream outf("data.txt");
  numsigns(5,outf);
  outf << endl;

  // print 3 $ to screen
  numsigns(3,cout);
  cout << endl;
}

Another option is to return a string from the function.

But before we get that fancy, let's consider a new loop:

int sum = 0;
for (int n=12; n > 0; n=n-1)
  sum = sum + n;

That's the sum of the numbers 1..12 (which is 78). We can see it as:

    12 + 11 + 10 + 9 + ... + 2 + 1

The sum grows as we add each number:

    0, 12, 23, 33, 42, 50, ...

This can be done recursively in much the same way. The trick is how to translate sum=sum+n to recursion.

Everything to the left of the assignment is what we will ultimately return. So that is a good hint that it is what your recursive function should return.

Everything to the right of the assignment is how we update the 'sum'. That is a good hint that it is where you recurse.

Let's try it.

int sum_to_n( int n )
{
  if (n = 0) return 0;  // nothing to sum, sum = 0
  return sum_to_n( n-1 ) + n;
}

See that?

return sum_to_n( n-1 ) + n
──┬─── ─────┬───────── ─┬─
  │         │          + n   (value to add to the accumulated sum) 
  │        sum               (the accumulated sum)
sum =                        (the new sum)

Now we can think about strings.

In a loop:

string s;
for (int n = 5; n > 0; n=n+1)
  s = s + '$';

Your task: write yourself a recursive function that returns a string (instead of an int) so that you can say:

int main()
{
  ofstream outf("data.txt");
  outf << repeat( '$', 5 ) << endl;
}

Hope this helps.

[sariki]

Well I got it working I appreciate you explaining it I guess I just didn't fully understand how to write out a Recursive Algorithm. So I appreciate that!

Here is a bit of a sample that I wrote to show you :)

if (n == 0) return;
	outf << '*';
	asterisks(n - 1, outf);
int main()
{	ofstream outf("out.ot");
	outf << "With 5 Asterisks you go!:" << endl;
	asterisks(5, outf);
	outf << endl;
	outf << "With no Aterisks you stop!" << endl;
	asterisks(0, outf);
	outf << endl;
	outf << "With 3 Asterisks you go slow!" << endl;
	asterisks(3, outf);
	outf << endl;
}