How can I make a recursive version of my iterative method?

Question

Greetings. I am trying to write a recursive function in Java that prints the numbers one through n. (n being the parameter that you send the function.) An iterative solution is pretty straightforward:

public static void printNumbers(int n){
    for(int i = 1; i <= n; i++){
         System.out.println(i);
         i++;
    }

As a novice programmer, I'm having troubles figuring out how a recursive version of this method would work. Any bright ideas? Thanks for reading my problem!

Answer 1

The recursive version needs two arguments (n and i) so make it an auxiliary non-public method and just call it from the public method to start the recursion going:

static void auxPrintNumbers(int n, int i){
    if(i <= n) {
        System.out.println(i);
        auxPrintNumbers(i + 1);
    }
}

public static void printNumbers(int n){
    auxPrintNumbers(n, 1);
}

Answer 2

Your iterative version has some problems: you are iterating i twice, in the for statement then again at the end of the loop; also you should let i < n be the ending condition of your loop.

To answer your question, obviously the recursive function will have to print out the current number and if the current number hasn't yet reached n, call itself again - so it must take the current number (which we're calling i in the iterative version) as a parameter - or the class needs to hold it as an instance variable, but I'd stick with the parameter.

Answer 3

public static void printNumbers(int n){
   if( n > 1 ){
      printNumbers(n - 1);
   }
   System.out.println(n);
}

This function calls itself recursively until it reaches n = 1. From this point all values are printed in correct order: 1, 2, 3, ...

Answer 4

You are using a for loop that is iterating from i=1 to n. As you want to do this with recursion and it is easier to pass n instead of i and n, we just reverse the whole thing, so we count down n to 1. To keep the order of the prints, we first call the recursive function and print the number after the execution:

public static void printNumbers ( int n )
{
    if ( n > 0 )
    {
        printNumbers( n - 1 ); // n - 2, if the "i++" within the for loop is intended
        System.out.println( n );
    }
}

For simple iterative -> recursive conversions it is easy to change loops into a format like this:

public static void printNumbers ( int n )
{
    int i = 1;
    while ( i <= n )
    {
        System.out.println( i );
        i++; // i += 2, if the "i++" within the for loop is intended
    }
}

Now you can easily transform that into a recursive function:

public static void printNumbers ( int n, int i )
{
    if ( i <= n )
    {
        System.out.println( i );
        i++; // i += 2, if the "i++" within the for loop is intended
        printNumbers( n, i );
    }
}

Everything else is optimization.

Answer 5

According to your function that prints every odd number from 1 to n the recursive function should look something like this:

public static void printNumbersRecursive(int n)
{
  if (n % 2 == 0) printNumbersRecursive(n - 1);
  else if (n > 0)
    printNumbersRecursive(n - 2);
  System.out.println(n);
}

if it is an error and that you'd want to print EVERY number from 1 to n then:

public static void printNumbersRecursive(int n)
{
  if (n > 0)
    printNumbersRecursive(n - 1);
  System.out.println(n);
}

Answer 6

A class version (just for fun):

class R {

  private final int n;

  public R (final int n) {
    if (n <= 0) {
      throw new IllegalArgumentException("n must be positive");
    }
    this.n = n;
  }

  @Override
  public String toString () {
    final StringBuilder sb = new StringBuilder();
    if (this.n > 1) {
      sb.append(new R(this.n - 1).toString());
    }
    sb.append(this.n).append(" ");
    return sb.toString();
  }
}

Used as:

System.out.println(new R(10));