Digging Deep into Java Recursion

Monday Jul 24th 2017 by Manoj Debnath
Share:

Unravel some key aspects of the recursive technique in the light of Java programming.

Recursion is an expression wherein each term is generated by repeating a specific pattern of the solution statement. It is an elegant way of constructing a solution statement for a certain type of problem. In fact, there are problems that are best described recursively. Even though recursive imposes a repetitive structure, it is not the same as the process of iteration, such as looping. The complexity of discerning the actual functionality of recursion lies in its taciturnity. This article tries to unravel some key aspects of this technique in the light of Java programming.

The Concept of Recursion

Problems that may be designated as recursive have certain common characteristics. Invocation of a recursive function actually solves the recursion in the simplest cases or the base cases. Any other case that is complex in that the base case is divided into two conceptual pieces—such as one again as the simple case, and another is the complex case—that the method does not know how to solve it. Therefore, the method itself is invoked again; this divides the problem again into two conceptual pieces. This "divide and conquer" strategy is repetitively applied until the problem remains no more complex that the base case. This initiates the point of return. However, it is obvious that, to make the recursion feasible, the latter piece must resemble the original problem, but a smaller version of it. The method keeps on copying itself distinctively with new parameters and local variable values with each call. This is referred to as recursive calls or recursion steps.

The recursion calls continue to execute dividing each new sub problem into two conceptual pieces. But, to eventually terminate, the method must return with the combined version of the result with each new call which finally converges on a base case. This is initiated when the method recognizes that the base case has been reached and starts combining the result with the previous copy of the method. This sequence of calls ends when the last combined result is returned back to the final caller.

There are basically two types of recursive calls or recursion: indirect recursive calls or indirect recursion, and direct recursive calls or direct recursion.

Direct recursion occurs when a method calls itself such, as the fact function invoking fact again.

long f(){
   ...
   f();
}

Indirect recursion occurs when a chain of method calls eventually led to the calling of the original method again.

long f(){
   g();
}

long g(){
   h();
}

long h(){
   f();
}

The feature of recursion is not restricted to any specific domain of language. Most programming languages support it in the form a method that can call itself. Recursion as a programming construct owes its origin to the mathematical model called Recursive Programming where each term of an expression is described in the form of the expression itself in a repetitive norm. There are some sets of problems, like finding the factorial of a number or generating the Fibonacci series, computing GCD, formulating dynamic programming solutions, and so forth, are best described recursively. That, however, does not mean that they cannot be solved in a normal iterative way; the point is that they are ideal to be described in a recursive form.

Mathematical Model

The mathematical model of repetitive self-invocation may be described as follows.

For example, the problem of calculating the factorial of a positive integer, say, n, is described as the product of all integers beginning from 1 to n, inclusively. Therefore, by using the following formula:

Calculating the factorial of a positive integer
Figure 1: Calculating the factorial of a positive integer

we can define a mathematical expression in a recursive pattern as follows.

Defining a mathematical expression in a recursive pattern
Figure 2: Defining a mathematical expression in a recursive pattern

The basis of the preceding recursive definition is 1! This is equal to 1. The other values of n! (for all n>1) are recursive, derived from the following:

Deriving recursive results
Figure 3: Deriving recursive results

By using the same definition, we can find the factorial of any positive number, such as 12. We may expand the idea as follows.

Expanding the previous idea
Figure 4: Expanding the previous idea

Because the number n!is defined as a positive integer, it will always converge to the base case. This is the crux of the matter of recursive programming.

Let's try another simple example, the sum of all the numbers between 1 to N, inclusively. We may express it mathematically as follows:

Expressing the idea mathematically
Figure 5: Expressing the idea mathematically

Observe the repetitive pattern; if we can formulate the idea and enable it to somehow call itself repetitively until the base case is reached, we easily can frame this solution in a recursive style.

Defining a Recursive Method in Java

As mentioned earlier, recursive programming is not a sole feature found in one programming language. In fact, most programming languages—if not all—support this technique. Java is no exception; it allows creating a method that can call itself, which is the basic requirement to create a recursive function. Syntactically, the signature or the structure of a recursive function is no different from any other normal non-recursive function.

The following Java code is an excerpt of the summation formula as discussed previously.

Sum of numbers between 1 and n Trace
public int sumOfN ( int n ) {
   int sum;
   if ( n == 1 )
      sum = 1;
   else
      sum = n + sumOfN   ( n - 1 );
   return sum;
}
sumOfN(4)
   sumOfN(3)
      sumOfN(2)
         sumOfN(1)
         return 1
      return 2 + 1 = 3
   return 3 + 3 = 6
return 4 + 6 = 10

Example 1

What happens here is that each invocation of the method creates an environment of its own, with its separate data spaces. The local variables are created and parameters are initialized afresh within the separate environment. It is as if each new call to the method creates a clone of the method with unique values of the local variables.

A recursive method will invariably have an if-else statement with one of its branches (usually the if section) signifying the base case. This base case acts as a form of backtracking the point where the return values stored in the stack upon each invocation are added to the final sum variable.

Suppose the main method invokes the sumOfN function with a parameter value of 1. Becaise the initial value is equal to the base case, the value 1is returned and no recursion occurs.

Now, if the sum method is invoked with the parameter value of 2, the sum is called again with a parameter value of (n-1) or 1. The recent call is a fresh one and is distinct from the first call. Therefore, each of the calls has new a parameter, n, and a new local variable, sum. In the recent call n = 1, in this invocation, the sum = 1 is returned without a further recursive call. The control now returns to the first version of the sumOfN method and the return value of 1 is added to the initial value n, which is 2. Therefore, the variable sum is assigned the value 3, which is the final value returned to main method.

Here is another example function that calculates the factorial of a positive integer. The program can be traced in a similar manner.

Recursive factorial function Trace
public long fact(int n){
   if(n == 1) return 1;
   return n * fact(n - 1);
}
fact(5)
   fact(4)
      fact(3)
         fact(2)
            fact(1)
            return 1
         return 2 * 1 = 2
      return 3 * 2 = 6
   return 4 * 6 = 24
return 5 * 24 = 120

Example 2

Here is an interesting recursive solution of the Koch snowflake implemented in JavaFX. The code is rewritten in JavaFX from the book Java Software Solutions by John Lewis and William Loftus, 7th Edition. Pearson.

package org.mano.examples;

import javafx.application.Application;
import javafx.scene.*;
import javafx.scene.canvas.*;
import javafx.scene.paint.Color;
import javafx.stage.Stage;

public class Main extends Application {

   private static final int CANVAS_WIDTH = 400,
      CANVAS_HEIGHT = 400;
   private static final int TOP_X = 200, TOP_Y = 20;
   private static final int LEFT_X = 60, LEFT_Y = 300;
   private static final int RIGHT_X = 340, RIGHT_Y = 300;
   private static final double SQRT = Math.sqrt(3.0) / 6;

   public static void main(String[] args) {
      launch(args);
   }

   @Override
   public void start(Stage primaryStage) throws Exception {
      primaryStage.setTitle("Koch snowflake");
      Group root = new Group();
      Canvas canvas = new Canvas(CANVAS_WIDTH, CANVAS_HEIGHT);
      GraphicsContext gc = canvas.getGraphicsContext2D();
      startPainting(gc);
      root.getChildren().add(canvas);
      primaryStage.setScene(new Scene(root));
      primaryStage.show();

   }

   private void startPainting(GraphicsContext gc) {
      int order = 5;
      // gc.setFill(Color.GREEN);
      gc.setStroke(Color.GREEN);
      gc.setLineWidth(1);
      drawFractal(order, TOP_X, TOP_Y, LEFT_X, LEFT_Y, gc);
      drawFractal(order, LEFT_X, LEFT_Y, RIGHT_X, RIGHT_Y, gc);
      drawFractal(order, RIGHT_X, RIGHT_Y, TOP_X, TOP_Y, gc);
   }

   public void drawFractal(int order, int x1, int y1, int x5,
         int y5, GraphicsContext gc) {
      int deltaX, deltaY, x2, x3, x4, y2, y3, y4;
      if (order == 1) {
         gc.strokeLine(x1, y1, x5, y5);
      } else {
         deltaX = x5 - x1;   // Distance between end points
         deltaY = y5 - y1;
         x2 = x1 + deltaX / 3;
         y2 = y1 + deltaY / 3;
         // One third
         x3 = (int) ((x1 + x5) / 2 + SQRT * (y1 - y5));
         y3 = (int) ((y1 + y5) / 2 + SQRT * (x5 - x1));
         x4 = x1 + deltaX * 2 / 3;
         y4 = y1 + deltaY * 2 / 3;
         drawFractal(order - 1, x1, y1, x2, y2, gc);
         drawFractal(order - 1, x2, y2, x3, y3, gc);
         drawFractal(order - 1, x3, y3, x4, y4, gc);
         drawFractal(order - 1, x4, y4, x5, y5, gc);
      }

   }

}

Output

The completed Koch snowflake
Figure 6: The completed Koch snowflake

Conclusion

Recursion is nothing but a method that calls itself repeatedly until the problem converges into its simplest form, called the base case. It applies divide and conquer strategy to achieve that and divides a problem into two conceptual forms. One of these form is known to the method how to solve, called the base case, and another which the method do not know hence makes a recursive call to break the problem further into smaller versions of it. This is the crux of the recursive function. If one closely observes, one will find that all recursive methods have a similar architecture. If the base case is reached, the method returns a result and the recursive call to itself is stopped. If the base case is not reached, the recursive calls continue.

Share:
Home
Mobile Site | Full Site
Copyright 2017 © QuinStreet Inc. All Rights Reserved