Converting Function to a Recursive Function

[AdrenaL]

Hey all. So the code I am posting works fine, but I am unsure how to make it recursive. Anytime i change the return to "return collatz(n*3+1)" or "return collatz(n/2)" I just always end up with "1" which is the final product, but none of the numbers in-between. Any ideas?

I am trying to print out each number as it is calculated. Correct output would be

What number do you want to begin with? 15
46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1

If z = 15.

I'm assuming I am going about recursion the wrong way, so any tips would help. I'm not looking for a solution - I want to do it myself - I've just been trying for the past few hours with no results.

#include <iostream>

using namespace std;

int collatz (int n)
{


		    if (n == 1 || n == 2)
		    {
		        return 1;
		    }
		    else
		    	if (n%2 == 1)
		    {
		    	return (n*3+1);
		    }
		    else
		    	if (n%2 != 1)
		        {
		        return (n/2);
		        }

}

int main()

{
	int z;
	cout <<"What number do you want to begin with?";
	cin >> z;

	do{
	z = collatz(z);
	cout << z;
	if (z > 1)
	{
	cout << ",";
	}
	}
	while (z > 1);

return 0;
}

[keskiverto]

Your main() should probably be:

int main()
{
	int z;
	cout <<"What number do you want to begin with?";
	cin >> z;

	collatz(z);
	cout << '\n';

	return 0;
}

What one function call does is compute the next number, show it, and call function with the number. Obviously, if the next number is 1, then there is no further call.

[Jamerack]

You don't need recursion inside collatz, just leave the do while loop around where you call collatz in main.

[keskiverto]

What if there is homework: "make a recursive ..."? Then there is a need.

[Jamerack]

Yes, if it is homework then there is a need for recursion, if the homework so states, but they said nothing about homework, so I stated that it is easier to use the do while loop.

[AdrenaL]

Recursion is not needed, however it is what I am trying to learn. I know it can be done as a recursive function, I'm just having trouble understanding how. It comes up with the final answer when I use

#include <iostream>

using namespace std;

int collatz (int n)
{


		    if (n == 1 || n == 2)
		    {
		        return 1;
		    }
		    else
		    	if (n%2 == 1)
		    {
		    	return collatz(n*3+1);
		    }
		    else
		    	if (n%2 != 1)
		        {
		        return collatz(n/2);
		        }

}

int main()

{
	int z;
	cout <<"What number do you want to begin with?";
	cin >> z;

	do{
	z = collatz(z);
	cout << z;
	if (z > 1)
	{
	cout << ",";
	}
	}
	while (z > 1);

return 0;
}

But I want it to output every number with each pass of the function, not just the final product. That's the reason for my do-while loop, is im trying to print out each number before the function runs again

[keskiverto]

Self-assigned homework.

if ( 1 == n || 2 == n )
{
  cout << "1\n";
  return;
}

int next = ...

cout << next << ',';
collatz( next );

[AdrenaL]

Yes, so far I'm not giving myself a very good grade!

I'm not following your last piece of code. Specifically the next variable. What would be returned from that to terminate the function? And are you suggesting another variable to store the old number for output before moving on?

Sorry, I only know the very basics of C++.

edit*************

So I changed around some things and incorporated your code and I now have a full working version (with recursion!)

Thank you so much for your help. Adding the extra variable was something I never thought about. Same with keeping the outputs in the function. Once again, I appreciate your time.

[keskiverto]

Good. I bet your solution differs from this:

void collatz( int n )
{
  if ( n < 3 )
    {
      cout << "1\n";
      return;
    }
  const int next = ( n%2 ) ? n*3+1 : n/2;
  cout << next << ',';
  collatz( next );
}

What we have there?

* A more fool-proof end condition: 0 and negative values will stop recursion too.

* Ternary operator ?

* n%2 is either 0 or 1. if (0) is same as if (false), and if (!0) is same as if (true). Therefore, in ternary the ( n%2 ) is same as ( 1 == n%2 ).

* A function returning void. We could have an explicit return; on line 11, but compiler adds it for us.

* This is tail recursion.

* Use of const. The 'next' is initialized, but not changed after that. We state that explicitly.


Note, you had essentially:

int foo()
{
  if ( condA ) return 7;
  else if ( condB ) return 42;
  // what if we get here?
}

Formally, both condA and condB could fail and a value returning function would have a branch that does not return a value.

On the other hand, you condA and condB were 1==n%2 and 1!=n%2. n%2 is always 1 or 0 and therefore exactly one of them is true for any positive n. That is why it is enough to have:

if ( 1==n%2 )
{
  // n is odd
}
else
{
  // n is even
}