Section 7.1 Basic Recursion
In this chapter, we will explore how to translate your recursive logic from Python to Java. While the core concepts of recursion remain the same, the syntax and a bit of the structure of your code will change somewhat.
As you may know from Python, recursion is a powerful problem-solving technique involving one or more base cases and recursive steps in which a function or method calls itself while moving towards a base case. When moving to Java, the core logic you’ve learned remains identical. The challenge is adapting that logic to Java’s statically-typed, class-based syntax.
Let’s take the familiar factorial function, which calculates \(n!\) (read as "n factorial"), so for example
\begin{equation*}
5! = 5 × 4 × 3 × 2 × 1 = 120.
\end{equation*}
Factorial is a classic example of recursion, where the function calls itself with a smaller value until it reaches a base case. In general,
\begin{equation*}
n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1\text{,}
\end{equation*}
or recursively defined as
\begin{equation*}
n! = n \times (n-1)!
\end{equation*}
with base cases \(0! = 1\) and \(1! = 1\text{.}\)
You may recall mathematical notation using the symbol \(\sum\) (Greek letter sigma) to represent "sum." For example, when we sum all elements in an array, we write
\begin{equation*}
\sum_{i=0}^{n-1} a_i\text{,}
\end{equation*}
where \(i=0\) below the symbol indicates we start at index 0, \(n-1\) above it means we end at index \(n-1\text{,}\) and \(a_i\) represents the array element at each index \(i\text{.}\) Similarly,
\begin{equation*}
\sum_{i=1}^{n} i
\end{equation*}
means "sum all integers \(i\) from 1 to \(n\text{.}\)"
Factorial involves multiplication rather than addition, so we use the product symbol \(\prod\) (Greek letter pi):
\begin{equation*}
n! = \prod_{i=1}^{n} i\text{,}
\end{equation*}
which means "multiply all integers \(i\) from 1 to \(n\text{.}\)" Both summation and factorial can be expressed recursively—summation as the first element plus the sum of remaining elements, and factorial as
\begin{equation*}
n \times (n-1)!\text{.}
\end{equation*}
Listing 7.1.1 is the Python implementation of the factorial function. It checks for negative numbers, defines the base case for 0! and 1!, and implements the recursive step.
Many Python programs organize related functions into classes. The same factorial function can be placed inside a class as a method instead of as a function. When this is done, you need to create an instance of the class in order to call the method. Below, we create the class
MathTools with a method factorial, and we call it from the main function.
Listing 7.1.2 is the Python implementation of the factorial function as a method within a class. It maintains the same logic as the previous function but is now encapsulated within a class structure.
See if you can spot the differences in the Java version below.
Listing 7.1.3 is the Java implementation of the factorial function. It follows the same logic as the Python version but adapts to Java’s syntax and type system.
Notice the key differences from Python: instead of
def factorial(n):, Java uses public static int factorial(int n) which declares the method’s visibility as public, that it belongs to the class rather than an instance (hence, static), the return type as integer, and the parameter type also as integer. The recursive logic—base case and recursive step—remains identical to Python, and, of course, all code blocks use curly braces {} instead of indentation.
You have attempted of activities on this page.
