12.2. How Recursion Works

A recursive function has two main parts:

1. Base Case: A condition that returns a value without making a further recursive call. This prevents the function from calling itself indefinitely.
2. Recursive Case: The part of the function where it calls itself with modified arguments.

A recursive function is designed to solve problems by calling itself. It consists of two important parts:

• Base Case: This is a conditional statement within the function. When this condition is true, the function stops calling itself and returns a value. This is essential to prevent infinite loops or calls that do not end.
• Recursive Case: This is where the function performs its main task. It calls itself with a different argument, typically one that brings it closer to the base case. Essentially, this part breaks the problem down into smaller issues.

Think of a recursive function like a set of Russian dolls. Each time you open a doll, you find a smaller doll inside. Eventually, you reach the smallest one, which can't be opened further — this is like the base case. While you’re opening each doll, you’re performing a task that resembles the recursive case.

Example: Let's take an example of calculating the factorial of a number. The factorial of a number n (denoted as n!) is defined as: ● n! = n * (n-1) * (n-2) * ... * 1 ● The factorial of 0 is defined as 0! = 1.

Factorial is a common example used to illustrate recursion. The factorial of a number n is the product of all positive integers up to n. The recursive definition is:

• For the base case, 0! (factorial of 0) is defined as 1.
• The recursive case defines n! as n multiplied by the factorial of n-1. This continues recursively until it reaches the base case.

Imagine you are stacking books. If you have 5 books, you can think of it this way: to stack all 5, you first place 1 book on the table, and then stack 4 more on top. The process repeats where you take 1 book off until there are none left. The factorial builds on itself in a similar way.

Factorial Function Using Recursion:

public class RecursionExample {
// Recursive function to find factorial of a number
public static int factorial(int n) {
if (n == 0) {
return 1; // Base case: factorial of 0 is 1
} else {
return n * factorial(n - 1); // Recursive case
}
}
public static void main(String[] args) {
System.out.println("Factorial of 5: " + factorial(5)); // Output: 120
}
}

In the implementation of the factorial function:

• The function factorial takes an integer n. If n is 0, it returns 1, which is our base case.
• Otherwise, it calls itself with n-1 and multiplies that result by n (the recursive case). This means that each call adds to a stack of calls until the base case is reached.

Consider layers of paint being applied to a wall. Each layer requires waiting until the previous one has dried. In our function, each multiplication waits for the next factorial computation to resolve, just as each layer waits for the one below it to dry before the wall can be fully painted.

--