A beginners’ tutorial on recursion in Java: Video Lecture 19

This article discusses the basics of recursion in Java. We will discuss the theory of recursion, how we can write a recursive method in Java, and how to trace a recursive program.

We are already familiar with how to use methods in Java. A method is a code snippet that you can call an arbitrary number of times from another method. This article explains how we can use a recursive Java method to solve a problem that we could solve using a loop.

In mathematics and computer science, recursion refers to a special technique to solve problems that are difficult to program using loops. The main property of recursion is that a recursive function defines itself, or at least a part of itself. In a recursive method, you will see that the method is calling itself at some point.

Recursion helps solve many complex problems that are difficult to solve using a loop, and at the same time when solving a portion of the problem is easy to tackle. 

Properties of recursion

A recursive method have two properties. 

1. A base case, or a stopping condition: Of course, we do not want our program to run forever. The recursion — that is the calling of itself — must stop at some point. The condition at which the recursion should stop is called the base case. The base case is generally an easy-to-solve subproblem of the main overarching problem.
2. A recursive call: In every call, the method must solve a part of the main problem. When the method calls itself, the call must receive a smaller problem than the problem the current method is handling. Structurally, the smaller problem should have the same properties as the current problem. Only the size of the problem should be smaller in the next call. In particular, we have to make sure that each call is moving the granulated subproblem toward the base case, which is the terminating condition.

A video lecture on recursion in Java

The following video lecture complemnts the content of this page. The video lecture explains the theory of recursion, covers the simple examples of this page, and provides a tracing of a recursive function to clarify the concepts.

A simple problem to explain recursion

Let us say that we have the following problem in hand. 

Write a recursive method that prints all the integer numbers between n and 1. That is, if n=5, we have to print

5 4 3 2 1

If n=3, then we have to print 

3 2 1.

A solution to the problem using a loop

We can easily solve this problem without any recursions. We can directly use a loop. Let us solve the problem with a loop first.

import java.util.Scanner;
class MyPrinter{
  public static void main(String[] args){
    Scanner myScanner = new Scanner(System.in);
    System.out.print("What is the value of n: ");
    int n=myScanner.nextInt();
    int i;
    for (i=n; i>=1; i=i-1){
      System.out.print(i+" ");
    }
    System.out.println();
  }
}

In the program above, we ask the user for the value of n. 

The loop variable i starts from n and decreases the value by 1 in each iteration. The execution keeps going inside as long as the value of the loop-variable i is greater than or equal to 1. That is, the loop terminates when the value of the loop-variable becomes smaller than 1.

Inside the loop, we have to print the content of the loop variable i, separated by spaces. 

After the loop ends, we write an empty System.out.println statement to make sure that the command prompt appears in the next line instead of in the same line, after the program outputs get printed.

Save the code in a file named MyPrinter.java, compile it using javac, and run it using java.

My Computer$ javac MyPrinter.java
My Computer$ java MyPrinter
What is the value of n: 5
5 4 3 2 1 
My Computer$ java MyPrinter
What is the value of n: 10
10 9 8 7 6 5 4 3 2 1 
My Computer$ java MyPrinter
What is the value of n: 3
3 2 1 
My Computer$ 

The output demonstrates that the program asked for the value of n. The user entered 5. The program printed.

5 4 3 2 1

After running the program again  — the program asked for n, the user entered 10, the program printed all the integer numbers from 10 down to 1.

The output shows another execution of the same program, where the user entered 3 as the value of n. The program printed

3 2 1

Therefore, the program worked perfectly.

We will solve the same problem, which is printing n integers from n down to 1, using recursion, without using any loop.

A solution to the problem using recursion

We will not use any loop at all. Rather, we will use a recursive method. Let us say that the name of the method is myRecurrence. The method myRecurrence will accept one parameter only, which is n, the number that the user provided. 

Here is the code that uses recursion and no loop.

import java.util.Scanner;
class MyPrinter{
  public static void main(String[] args){
    Scanner myScanner = new Scanner(System.in);
    System.out.print("What is the value of n: ");
    int n=myScanner.nextInt();
    myRecurrence(n);
    System.out.println();
  }
  
  static void myRecurrence(int n){
    if (n<1){
      return;
    }
    System.out.print(n+" ");
    myRecurrence(n-1);    
  }
}

The header of the recursive method, myRecurrence

The return type of myRecurrence is void because it does not need to return anything to the caller. The method has only one parameter. The name of the parameter is n. This parameter n, for the first call from the main method, will hold a copy of the n that the user enters.

Recall from the previous video lecture that the header must start with the word static because we will call the method from the main method, which is a static one.

The base case in myRecurrence

As said earlier, in recursion, there must be two items — a base case and a recursive call. 

A base case is a terminating condition. In this case, our terminating condition is — when n is less than 1. That means, when n is less than 1, we should do nothing but return to the caller because there is nothing else to do. Remember that we have to print up to 1. We do not print anything smaller than 1. 

We write the base case using an if statement. If we find that n is lesser than 1, we say return.

Inside myRecurrence, the base case is written as:

    if (n<1){
      return;
    }

A return statement with an immediate semicolon, in the above base case, indicates a return of execution without any value. Given that the method has a void return type, all we can return is the execution without any content. We have a base case now.

Other recursive properties in myRecurrence

In a recursive method, a part of the whole work will be solved here within the method. The rest of the work, which is smaller in size, will be solved in a different call of the same method.

In this particular body of the method, we solve the problem of printing one number only, which is whatever value came via the parameter n. 

We simply print n and then put a space. The space is to make sure that there is a gap between the current number printed and the number we will print next. In the method, we wrote:

    System.out.print(n+" ");

Now, the task left is — printing the rest of the numbers. Let us assume we don’t know how to print the rest of the numbers. Again, we have printed n, but we do not know how to print the rest of the numbers, which are n-1, n-2, n-3, so and so forth.

If n is equal to 5, we have printed 5. The rest of the numbers that we need to print are 4, 3, 2, and 1. We do not know how to print them, but we have a method, which is the same method myRecurrence that can print a sequence of numbers down to 1.

What we do is, we call myRecurrence with n-1 as the parameter. That is, if n is 5 in the current method, we are sending 4 as the parameter for the next call.

We write the following line to print all the numbers starting from n-1:

    myRecurrence(n-1);   

Note again – we have a base case. We solve the problem partially within the method. We send the rest of the problem, that is the smaller subproblem to the next call.

The output of the recursive program

Let us save the program, compile it, and execute it.

Like when we used a loop, the program asks for the value of n. The user enters 5. The program prints:

5 4 3 2 1

The same outputs are observed with n=10 and n=3.

Tracing the program

The video above provides tracing of the code with n=3. It is important to trace a code using pen and paper for two main reasons: (1) tracing slowly helps understand the problem well, and (2) tracing helps in finding logical errors in the code. I suggest that the reader watches the video above to enjoy the tracing of the recursive method we have discussed in this article.

Another recursive problem

As a quick bonus teaser program, let us discuss the solution to another problem, which is relevant to the one that we have discussed above.

Using recursion, write all the integer numbers between 1 and n. That is, if n=5, we have to print

1 2 3 4 5

If n=3, then we have to print 

1 2 3

Notice that in the previous program, we wrote all the numbers in reverse order. When n was 5 we printed 5 4 3 2 1. Now, we are printing 1 2 3 4 5.

How can we change the previous recursive program to print everything in ascending order?

In the previous problem, we first printed n, and then using another recursion, we printed all the numbers from n-1 down to 1. 

Now, when we go inside the recursive method, we cannot print anything before printing the rest of the numbers. That is, when n is 5, we have to wait till all the other numbers 1, 2, 3,  and 4 are printed.

When n is 4, we have to wait till all the numbers 1, 2, 3, are printed.

When n is 3, we have to wait till all the numbers 1, and 2, are printed.

So and so forth.

We can accomplish by switching these two lines of the previous myRecurrence method.

    System.out.print(n+" ");
    myRecurrence(n-1);   

That is, we can print all the numbers by flipping the above two lines to the following:

    myRecurrence(n-1);   
    System.out.print(n+" ");

The solution

Here is the complete code that prints the numbers in ascending order (1 to n.)

import java.util.Scanner;
class MyPrinter{
  public static void main(String[] args){
    Scanner myScanner = new Scanner(System.in);
    System.out.print("What is the value of n: ");
    int n=myScanner.nextInt();
    myRecurrence(n);
    System.out.println();
  }
  
  static void myRecurrence(int n){
    if (n<1){
      return;
    }
    myRecurrence(n-1);  
    System.out.print(n+" ");  
  }
}

After the base case, in the modified myRecurrence method, we go to recursion without printing n. Numbers smaller than n are processed first. The System.out.print statement will print n, after all the smaller numbers are processed.

If we save this file, compile it, and run the program, we will see that the program is printing all the numbers between 1 to n in ascending order.

My Computer$ javac MyPrinter.java
My Computer$ java MyPrinter
What is the value of n: 5
1 2 3 4 5 
My Computer$ java MyPrinter
What is the value of n: 10
1 2 3 4 5 6 7 8 9 10 
My Computer$ java MyPrinter
What is the value of n: 3
1 2 3 
My Computer$ 

Tracing the program

I suggest that you trace this modified program, to print all numbers in increasing order, using paper and pencil. Again, tracing your code using paper and pencil helps develop an understanding of the logical flow of a program.

When is recursion used?

You might think – why on earth we have solved this simple problem using recursion? The answer is — we have used this simple problem to explain how recursion works. In practice, recursion is used for problems that are hard to code using loops.

There are problems for which it is easier to write a recursive solution than writing a loop-based solution. In games, where it is required to keep track of the status of a game board or in artificial intelligence, where it is required to foresee possible changes, recursion is used because it automatically saves the local variables in each call.

Exercise questions

Question 1: Write a recursive method that takes n as its parameter and then returns 1+2+3+ … … … +n for any n>0.

Question 2: Write a recursive method that takes n as its parameter and then returns the factorial of n for any n>=0. (The factorial of n is referred to as n! and n!=n*(n-1)*(n-2) … … 2*1.) As an example, 5!=5*4*3*2*1=120. Factorial of zero is considered 1. That is 0!=1.

Concluding remarks

If you have not yet subscribed to Computing4All.com or to our YouTube channel, please do so to receive notifications on our new articles and videos.