Beyond Loops: Unleashing the Power of Recursion in Programming

Recursion

What is recursion?

Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially. Usually recursion involves a function calling itself.

Laws of Recursion

1- A recursive algorithm must have a base case.

2- A recursive algorithm must change its state and move toward the base case. (break down of problem)

3- A recursive algorithm must call itself, recursively.

Every recursive problem must follow aforementioned Law. Let's take a simple example and try to understand these Laws.

Problem: Calculate the sum of a given list.

list = [1,2,3].

One way of solving this problem is using loops which is the iterative way of doing it. Let's Pretend for a minute that you do not have while loops or for loops. How would you compute the sum of a list of numbers?

Answer is recursion. Let's apply Recursion Law here.

Law1: How to identify base condition. Ask question to ourself what would be the smallest size of list which we can generate for the given list.

a) [1,2,3]

b) 1 + [2,3]

c) 1 + 2 + [3].

d) 1+ 2+ 3 + EMPTY_LIST.. beyond the empty list we can not reduce the size of list. Now the question is what would be answer if LIST is EMPTY -> 0.

This is our base case.

Law2: As we clearly saw we were reducing the size of list to identify the smallest list -> which means Problem Can Be Divided into Smaller Subproblems:

Law3: Final law is that the algorithm must call itself, be it a smaller or bigger problem, same set of steps are required to solve the problem.

public static int calculateSum(List<Integer> list) {
        // Base case: if the list is empty, return 0
        if (list.isEmpty()) {
            return 0;
        } else {
            // Recursive case: sum the first element with the sum of the rest of the list
            return list.get(0) + calculateSum(list.subList(1, list.size()));
        }
    }

Patterns

Identifying when recursion is applicable in a problem involves recognizing certain patterns or characteristics that suggest a divide-and-conquer approach, where a problem can be broken down into smaller, simpler subproblems. Here are some indicators that recursion might be a suitable approach:

1. Problem Can Be Divided into Smaller Subproblems:
2. Solving a Problem Involves Solving the Same Problem with Different Input:
3. Applying the Problem to Itself Simplifies the Solution:
4. The Problem Exhibits Overlapping Subproblems:
5. The Problem Has a Recursive Definition:
6. Hierarchical or Tree-like Structure:
7. Backtracking Scenarios:
8. Expression Evaluation:
9. Recursive Data Structures:
10. Natural Decomposition:
11. Divide-and-Conquer Paradigm:
12. Observing a Pattern in Recursive Solutions: