What Is a Recursive Function, and How Do You Create One in Java?

The need to repeat code can never be underestimated in the search for solutions to some of the world’s biggest problems. What you need to know is that in programming, repetition takes one of two forms—iteration or recursion.

The goal here is to introduce you to repetition in code and demonstrate how it can be used to enhance your Java programs.

Repetitive programs can help you to solve some of the most difficult programming problems. Here’s what you need to know to create recursive programs in Java.

Using Iteration

Iteration uses a loop structure to repeat code. The three types of iterative structures are pre-test loop (while), post-test loop (do-while), and counter-controlled loop (for).

These iterative structures operate by repeating a block of code while a specific condition remains true, but as soon as that condition becomes false the loop stops and the program returns to its normal flow.

For example, we could employ one of the iterative structures to solve the problem of the sum of all integers from 1 to n. Depending on the iterative structure that is used the solution will take a specific form, but any of the three iterative structures can provide a solution for this problem using the following pseudocode.

Iteration Pseudocode Example


START
DECLEARE sum, count as integer
sum = 0
count = 1
REPEAT
   Sum = sum + count
   Count = count + 1
UNTIL count > n
END

The pseudocode above has two variables, sum and count, that are initialized to 0 and 1 respectively. The "count" variable is initialized to 1 because the problem that we are trying to solve states that we need the sum of all integers from 1 to n.

The variable “n” will be assigned a random number from the user and the “count” variable will increase by one each time a loop is performed, but as soon as the value of the “count” variable exceeds that of “n” then the loop will stop.

Why Use Recursion?

If we were to examine the facts surrounding iteration and recursion, we will find several things to be true.

Both methods involve repetition.
Both methods require a test condition, which will indicate when to stop.
Both methods can theoretically execute forever if an exit condition isn’t given or met.
Any problem that can be solved using iteration can also be solved using recursion and vice versa.

So why would we want to choose one method over the other? The simple answer is efficiency. With recursion, a programmer can use less code to achieve what is essentially the same result. Less code means that there is a significant decrease in the possibility of errors going unnoticed.

Recursion uses more memory and is slower than iteration, but has a built-in stack (data structure). With iteration you would have to build a data structure (essentially reinventing the wheel), leaving your program open to a greater possibility of uncaught errors due to the extra code.

How Does Recursion Work

Recursion is the name given to a process where a function repeatedly calls itself until a specific condition is met. This repetitive method solves problems by breaking them down into smaller, simpler versions of themselves.

Every recursive function consists of two parts—base case and general case.

Basic Structure of a Recursive Function Example


Function(){
//base case
//general case
}

The base case is the section of the recursive function that solves the problem. So, whenever the recursive function arrives at the base case the program exits the recursive function and continues with its natural flow.

The general case is the section of the recursive function that is repetitive. This is where the function calls itself and where the bulk of the work is done.

Using Recursion in Java

Some programming languages only support iteration, while others only support recursion. Fortunately, Java is one of the languages that support both repetitive methods.

In Java recursion is used in much the same way that it is used in any other language that supports it. The key is to always ensure that your recursive function has both a base and a general case, in that order.

Let’s go back to our initial summation example, the goal is to find the sum of all integers from 1 to n, where n is an integer number supplied by the user.

Java Recursion Example


//recursive function
int Sum(int n){ 
   //base case
   if (n <= 1){
   return 1;
   }
   //general case
   else{
   return n + Sum(n-1);
   }
}

The recursive function above takes an integer “n” and only terminates its execution when the value of n is less than or equal to 1.

If we were to pass the integer 5 to the program above, the variable "n" would assume the value of 5. The value of “n” would then be checked in the base case, but given that 5 is greater than 1 “n” will now be passed to the general case.

In this example, the general case will call the recursive function four times. On the final function call the value of “n” will be 1, effectively meeting the requirements of the base case resulting in the termination of the recursive function and returning 15.

If we change the value of “n” to 7, the recursive function will call itself six times and return 28 before terminating its execution.

Want to try it for yourself? You can execute the recursive program above by using the following line of code in the main function of your Java program.


System.out.println( Sum(7));

What You Learned

If you made it through this entire article you now have a basic understanding of the two repetitive methods that are used in programming. You now recognise the similarities between iteration and recursion and why a developer would choose to use recursion over iteration, and how to use a recursive function in Java.

Image Credit: ThisIsEngineering/Pexels

source https://www.makeuseof.com/what-is-a-recursive-function-and-how-do-you-create-one-in-java/