# Digging Deep into Java Recursion

*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:

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

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

**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:

**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.

**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:

**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 *1*is 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, 7^{th} Edition. Pearson.

packageorg.mano.examples;importjavafx.application.Application;importjavafx.scene.*;importjavafx.scene.canvas.*;importjavafx.scene.paint.Color;importjavafx.stage.Stage;public classMainextendsApplication{private static final int= 400,CANVAS_WIDTH= 400;CANVAS_HEIGHTprivate static final int= 200,TOP_X= 20;TOP_Yprivate static final int= 60,LEFT_X= 300;LEFT_Yprivate static final int= 340,RIGHT_X= 300;RIGHT_Yprivate static final double= Math.SQRTsqrt(3.0)/ 6;public static void main(String[]args) {launch(args);}@Overridepublic void start(Stage primaryStage) throwsException{primaryStage.setTitle("Koch snowflake"); Group root =newGroup(); Canvas canvas =newCanvas(,CANVAS_WIDTH; GraphicsContext gc = canvas.getGraphicsContext2DCANVAS_HEIGHT)(); startPainting(gc); root.getChildren().add(canvas); primaryStage.setScene(newScene(root)); primaryStage.show();}private void startPainting(GraphicsContext gc) {intorder = 5; // gc.setFill(Color.GREEN); gc.setStroke(Color.; gc.setLineWidthGREEN)(1); drawFractal(order,,TOP_X,TOP_Y,LEFT_X, gcLEFT_Y); drawFractal(order,,LEFT_X,LEFT_Y,RIGHT_X, gcRIGHT_Y); drawFractal(order,,RIGHT_X,RIGHT_Y,TOP_X, gcTOP_Y);}public void drawFractal(intorder,intx1,inty1,intx5,inty5, GraphicsContext gc) {intdeltaX, 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

**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.