Recursion to Print and Count

Hi, so for an assignment I have to print out all the odd numbers between an inputed number and 0, and then print out a count of how many numbers there are, using only a recursive method (named int odd (int n). I have the printing working, I just can't seem to get the count to work. What am I doing wrong?

Code :

public static int odds(int n)
{
if (n%2==0)
{
n=n-1;
}
if (n==1)
{
System.out.print("");
}
else
{
System.out.print(n+" ");
n=odds(n-2);
count++;
}
return n;
}

Re: Recursion to Print and Count

Why didn't you show that code that almost or partly worked? I don't see any recursion here, and what is the method evens()?

Re: Recursion to Print and Count

Sorry, I wrote the method down wrong in the recursive statement. I am now also only showing the method that does work, but does not print out the count. I just don't understand how to print out a count of the odds.

Re: Recursion to Print and Count

On one hand, you're very close. On the other hand, there are some things I would do differently:

1. Some recusive methods return a value. This one doesn't need to.

2. The base case should be clearly defined for clarity. Your base case is defined by default and (I'm assuming) is dependent on the main() method to complete the method by printing the final odd value, 1. That's non-standard.

3. The code can be tightened up quite a bit.

As for maintaining and printing the number of odds, since each call to a recursive method starts that method anew, the variable count can't be declared inside the recursive method. I think you've figured that out, but we can't see where count is defined or initialized. The total count can be incremented and printed by the recursive method, however.

This is how I would do it:

Code java:

// method odds2() prints and counts the number of odd numbers from the
// given parameter int n to 0
// count is a class variable
public static void odds2( int n )
{
// the base case - stop at this condition
if ( n <= 0 )
{
// print the number of odds and exit the method
System.out.println( "The number of odds is: " + count );
return;
}
// if n is odd, print it and count it
if ( n % 2 != 0 )
{
System.out.print( n + " " );
count++;
}
// continue to process odds until the base case
odds2( --n );
}

Re: Recursion to Print and Count

There is one improvement I would do on your code GregBrannon as your current code executes at O(n)

Code :

// method odds2() prints and counts the number of odd numbers from the
// given parameter int n to 0
// count is a class variable
public static void odds2( int n )
{
// the base case - stop at this condition
if ( n <= 0 )
{
// print the number of odds and exit the method
System.out.println( "The number of odds is: " + count );
return;
}
// if n is odd, print it and count it
if ( n % 2 != 0 )
{
System.out.print( n + " " );
count++;
// If you are in this method you can safely say that the first odd was found.
// When you find the first odd you can subtract by 2 and the next number is still odd.
// This cuts down O(n) to O(n / 2) so it cuts down on how many times the method calls itself.
odds2(n - 2);
}
// continue to process odds until the base case
odds2( --n );
}

Also I agree it all depends where he declared his "count" variable. If it is declared in the main method then he will have to have a return value.

Code :

// base case return 0
// Odds return odds(n - 2) + 1
// Default return odds(--n)

Re: Recursion to Print and Count

Agreed. Thanks for the optimization. It had occurred to me, but I was already overstepping the bounds a bit - except the OP was sooooo close.