Recursion in Java: Another beginners’ guide: Video Lecture 20

This post is a continuation of the previous video lecture on Recursion. The current post and the associated video lecture explain more on recursion in Java. We target the following problem — how to compute the summation of all the integer numbers between 1 and n, using recursion.

Recall from the previous post that we can go over a series of numbers using recursion. In the previous lecture, we used recursion to print all the integer numbers between 1 and n. The recursive method had a void return type. That is, the method did not return any value but the execution only. In the current post, the recursive method has an int return type.

The problem description

In the current post and the in the video, we apply a mathematical operation (summation) over a series of integer numbers. The recursive method in the current post has an integer return type. Basically, we are solving an exercise question that I provided in the previous post.

Again, the exercise question we are targeting is — Add all the numbers between 1 and n, of course, using recursion. A condition is: n>0.

We can write the series of integer numbers as:

1+2+3+4+… … … +n

Also, instead of writing 1+2+3+4+ …. +n, we can rewrite the series as

n+ ….. … … +4+ 3+ 2+1

That is, I can write the numbers backward, without changing the content of the series.

We can put some more values, in terms of n, here in the sequence. It is just inclusion of more terms of n in place of some of the dots. The series is the same as before.

n+(n-1)+(n-2)+ ….. … … +4+ 3+ 2+1

Note that, n is the largest number in the series. The next number is one less than n, which is (n-1). The number after that is 2 less than n. Therefore, it is (n-2), so and so forth. The numbers added in the series become smaller and smaller, ending with 4+3+2+1.

We do not add anything smaller than 1 in the series because there is a condition with the problem description that n>0. That means, any number in the series has to be greater than 0 because any number can be considered n since it is the variable to this problem.

Recursion in Java: The associated video lecture

The following video lecture contains a video-version of this post.

Looking at a series as a function

Let us say that the function that sums up all the integer numbers between 1 and n is called adder. adder is a function of n. We write it as the word adder, and then within parenthesis we write (n). That is the function is written as adder(n).

We write:

adder(n)=n+ ……… +4+ 3+ 2+1

Or, adder(n)=n+(n-1)+(n-2)+ ….. … … +4+ 3+ 2+1

An iterative solution

It is easy to write a method to implement the function adder(n) using a loop. Let us write a Java method that implements the iterative adder(n) function.

import java.util.Scanner;
class Summation{
  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 s=adder(n);
    System.out.println("The summation is: "+s);
  }
  static int adder(int n){
    int sum=0;
    int i;
    for (i=n; i>0 ; i=i-1 ){
      sum=sum+i;
    }
    return sum;
  }
}

Notice that the method adder in the code has a for-loop that helps iterating over all the integer numbers starting from n ending at 1. The loop adds each number to the sum variable during the iterations. The method returns the integer, sum, which holds the summation of all the numbers.

Note from a previous lecture on methods that we have to declare the adder method as a static one, because we are calling adder from the main method, which is a static one.

The output of the iterative solution

Let us save the file, compile it, and run it. Here is the output.

My Computer$ javac Summation.java 
My Computer$ java Summation
What is the value of n: 5
The summation is: 15
My Computer$ java Summation
What is the value of n: 100
The summation is: 5050
My Computer$

Notice that the user enters n equal 5 and the program prints 15, which is the summation 5+4+3+2+1.

The user enters 100 in place of n and the program prints 5050, which is the summation of all the integer numbers between 1 to 100.

The program is working perfectly. However, the problem description states that we should not use a loop, rather we should use recursion to solve this problem.

Therefore, let us change the method adder in such a way that it does not contain any loop.

Looking at a series as a recursive function

We already wrote an iterative method static int adder(int n), as our solution. We need to modify that method to get rid of the loop.

Here is the sequence we want to code:

n+(n-1)+(n-2) ….. … … +4+ 3+ 2+1

As explained before, at first we have n. The next number is one less than n, which is n-1. The number after that is 2 less than n. Therefore, it is n-2, so and so forth. Finally, the numbers added become smaller and smaller, such as, 4, 3, 2, and 1.

Mathematically,

adder(n)= n+(n-1)+(n-2)+ ….. … … +4+ 3+ 2+1

Now, notice that, the part that contains (n-1)+(n-2) ….. … … +4+ 3+ 2+1, can be considered adder(n-1).

Hence, we can write

adder(n)=n + adder(n-1)

adder(n-1) already has every term from n-1 down to 1 in it. Therefore, adding n with adder(n-1) will give adder(n).

As an example, when n=5:

adder(5)=5+4+3+2+1

With n=4, adder(4)=4+3+2+1

Therefore, we can replace the 4+3+2+1 part of the adder(5) equation, by adder(4)

That is, we can rewrite:

adder(5)=5+adder(4)

therefore, the general equation is:

adder(n)=n + adder(n-1)

Notice that the above mathematical definition of adder(n) is already a recursive equation. In the left side, we have the function adder with parameter n. In the right side we have the same function “adder” but with a smaller parameter, (n-1).

The problem description already states that n should be greater than 0. That means, if the recursion ever reaches to a parameter with value 0, we should return something that does not contribute to the summation. Something that does not contribute to a summation is zero. That mean, no harm is done if we add 0 to anything. Therefore, we will return a 0 instead of further going inside another recursion, when the parameter itself is 0. Hence we have a base case, which is returns 0 when n becomes smaller than 1.

Let us code the items we discussed.

The recursive solution to the problem

We need to delete the loop entirely from the method adder of the iterative solution. Let us keep the sum variable. The variable sum now should be n+adder(n-1) based on our discussion above. We are still returning sum, just like when we had a loop. The recursion will do the work of looping.

The recursive solution is as follows. We only made changes to the adder method.

import java.util.Scanner;
class Summation{
  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 s=adder(n);
    System.out.println("The summation is: "+s);
  }
  static int adder(int n){
    if (n<1){
      return 0;
    }
    int sum=0;
    sum=n + adder(n-1);
    return sum;
  }
}

The following part of the adder method is the base case.

    if (n<1){
      return 0;
    }

The line

sum=n + adder(n-1);

has the recursive call to adder, where (n-1) portion of the problem is solved. That is, one adder method performs one addition only; the rest of the additions are performed in other recursive calls.

The output of the recursive solution

The output of the recursive program is no different than its iterative version. Note that we solved the same problem using iterative and recursive solutions. Therefore, their outputs for the same n will be the same.

Tracing the recursive solution

I highly suggest that you watch the YouTube video above to view how I traced the program for n=3. After watching the video, trace the program with n=4 and n=5, as a practice.

As I said in the earlier lecture, many sophisticated algorithms in artificial intelligence rely on recursion because recursion automatically saves the local variables and the parameters in each call. If you trace the recursive version of the program we have written in the current post, you will see that n has different values in each call.

The reality of a recursive solution

Recursion is an elegant technique. The reality of recursion is that you will prefer an iterative solution over a recursive one if the iterative one is easy to code. Sometimes, recursive solutions are easier to code but can be slower than its iterative version.

The tradeoff between ease of coding and how fast your program runs is a topic that is generally discussed in an Algorithms course. The specific topic is known as algorithm complexity. May be, some day we will discuss about algorithm complexity too.

For now, let us keep practicing and developing our programming skills.

Concluding remarks

If you have not yet subscribed to Computing4All.com and to our YouTube channel, please do so to receive notifications on our new articles and videos. Let us know if you have any questions via comments below.