Skip to content
Recursion
Summary - Recursion
Introduction to Recursion
Recursion occurs when a function calls itself to tackle smaller portions of the same problem.
In a recursive process, each call to the function is a step or iteration that works on a smaller piece of the problem, and the recursion proceeds until it reaches a base case.
The Factorial Function: A Classic Example
The factorial of a number, denoted by n!, is the product of all positive integers up to n. Notably, the factorial of 0 is defined as 1.
Factorials beautifully illustrate recursion because calculating n! inherently involves computing (n-1)!, (n-2)!, and so on, down to 0!.
Implementing Recursion in Java
To embody recursion in code, we require two key components: a base case and the recursion logic. The base case acts as a stop signal, preventing infinite recursion, while the logic addresses the smaller segments of the problem.
Coding the Factorial Function
We'll create a class named Factorial with a method calculateFactorial that calculates the factorial of a given number n.
public class Factorial {
public int calculateFactorial(int n) {
// Base case
if (n == 0) {
return 1;
}
// Recursive call
return n * calculateFactorial(n - 1);
}
public static void main(String[] args) {
Factorial fact = new Factorial();
int n = 5; // Let's calculate 5!
System.out.println("Factorial of " + n + " is: " + fact.calculateFactorial(n));
// Testing with another value
n = 10; // Now calculating 10!
System.out.println("Factorial of " + n + " is: " + fact.calculateFactorial(n));
}
}
In this example, calculateFactorial method demonstrates recursion. The function continually calls itself with n-1 until n equals 0, at which point it returns 1—satisfying the base case.
Understanding the Flow
For calculateFactorial(5), the process unfolds as follows:
image.png failed to upload
Each step solves a smaller instance of the problem, ultimately boiling down to the base case that halts further recursion and begins the process of returning values back up the chain.
Understanding Function calls in Java
To fully grasp this concept, it's essential to understand two fundamental data structures: Queue and Stack.
Queue and Stack: Basics
Stack in Action
Stacks are pivotal in managing function calls in Java. When a function calls another, Java essentially "pauses" the calling function, storing its state on the stack until the called function completes. This process uses the LIFO principle, where the most recently called function is completed first.
Call Stack: The Function Manager
The Call Stack is a specialized stack that tracks function calls within a program. Each function call adds a new frame to the stack (push), and upon completion, the frame is removed (pop). This ensures that functions resume and complete in the correct order, following the LIFO principle.
Stack vs. Heap Memory
Function Execution and Memory Management
Java uses stack memory to manage function executions:
Understanding Call Stack
Call stack is a pivotal structure used to store information about active methods in a program. It's essentially where the magic of function calls and returns is managed. When a function is called, a new frame (or activation record) is added to the call stack, and when the function completes, its frame is removed.
Activation Record
Each frame, or activation record, contains crucial details like the return address, parameters, and local variables. This systematic approach ensures that every function call is tracked, allowing Java to execute multiple functions seamlessly and maintain the state of each.
Recursive Function Calls and the Call Stack
To visualize how recursive function calls are managed, let's revisit our factorial function from a previous lesson. With each recursive call, a new activation record for the function is pushed onto the call stack. Once a function completes, its record is popped off, and Java moves back to the previous function call.
A Closer Look at the Process
The Significance of the Stack in Recursion
The stack's LIFO nature is perfectly suited for managing recursive calls. It ensures that the most recent function call is addressed first, allowing for an orderly return process that adheres to the function's logic and dependencies.
Deep Dive into Recursion
Understanding the Fibonacci Series
The Fibonacci series is a sequence where each number is the sum of the two preceding ones, starting from 0 and 1. So, it goes like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The challenge here is to find the nth number in this series using a recursive function.
Setting Up the Recursive Function
To solve this problem recursively, we need to identify two key elements: the base condition and the recursive logic.
The Base Condition
In any recursive function, the base condition is critical. It's the condition that stops the recursion. Without it, you'll fall into infinite recursion, leading to a stack overflow error. This error occurs when the call stack, a memory structure managing function calls, runs out of space due to too many recursive calls.
For the Fibonacci series, our base conditions will be straightforward:
These conditions handle the simplest cases in the Fibonacci series, allowing the function to have a clear stopping point.
Recursive Logic for Sub-problems
The Fibonacci series is built on a beautiful recursive pattern. To find the nth number, we look at the (n-1)th and (n-2)th numbers. This relationship forms the core of our recursive logic:
fib(n) = fib(n-1) + fib(n-2)
With this formula, we can break down the problem into smaller, manageable parts, where each part is a reduced version of the original problem.
Writing the Recursive Function
Let's write our function fib(int n) in Java. This method takes an integer n and returns the nth Fibonacci number. Inside the function, we implement our base conditions and recursive logic as discussed.
However, a direct implementation like this leads to repeated calculations, which can be inefficient, especially for larger values of n.
Introducing Memoization for Efficiency
Memoization is a technique to avoid redundant calculations by storing previously solved sub-problems. When a sub-problem needs solving, the function first checks if the solution is already stored. If so, it uses the stored value; if not, it calculates and then stores the solution for future use. This method drastically increases efficiency by reducing unnecessary calculations.
Here's a glimpse into implementing memoization:
Understanding these Java concepts helps in building efficient, modular, and maintainable software systems. For more detailed information, refer to the Notion link:
Want to print your doc?
This is not the way.
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.