Methods, Arrays, and Program Structure

Introduction to Recursion

ReadingPreview

আপনি একটি free preview lesson দেখছেন।

Lesson Overview

So far, যখন কোনো কাজ বারবার করতে হয়েছে, আমরা সাধারণত loops ব্যবহার করেছি।

Example:

for (
        int i = 1;
        i <= 5;
        i++
) {
    System.out.println(
            i
    );
}

কিন্তু repetition-এর আরেকটি important technique হলো:

Recursion

Recursion happens when a method calls itself, directly or indirectly, to solve a smaller version of the same problem।

Example:

static void countDown(
        int number
) {
    if (number == 0) {
        return;
    }

    System.out.println(
            number
    );

    countDown(
            number - 1
    );
}

এই lesson-এ আমরা শিখব:

What recursion means
Recursive method calls
Base case
Recursive case
How recursive execution unfolds
Call stack intuition
Countdown example
Factorial
Sum from 1 to n
Recursive array processing
Infinite recursion
StackOverflowError
Recursion vs loops
When recursion is useful
When iteration is simpler

Recursion algorithms এবং trees-এর জন্য খুব useful, কিন্তু এটাকে সব problem-এর default solution হিসেবে ব্যবহার করা উচিত নয়।

What Is Recursion?

Recursion is a technique where a method solves a problem by calling itself with a smaller or simpler input।

Basic structure:

static void recursiveMethod(
        int value
) {
    if (
            someStoppingCondition
    ) {
        return;
    }

    recursiveMethod(
            smallerValue
    );
}

A correct recursive solution normally needs two important parts:

Base case
Recursive case

Base Case

The base case tells recursion when to stop।

Example:

if (number == 0) {
    return;
}

Without a stopping condition, the method may keep calling itself indefinitely until the call stack runs out of space।

Recursive Case

The recursive case is where the method calls itself with a smaller problem।

Example:

countDown(
        number - 1
);

If current input is:

the next call receives:

then:

Eventually the base case is reached।

First Recursive Example

public class Main {

    public static void main(String[] args) {
        countDown(
                5
        );
    }

    static void countDown(
            int number
    ) {
        if (
                number == 0
        ) {
            return;
        }

        System.out.println(
                number
        );

        countDown(
                number - 1
        );
    }
}

Output:

Trace the Calls

The method calls happen like this:

countDown(5)
↓
countDown(4)
↓
countDown(3)
↓
countDown(2)
↓
countDown(1)
↓
countDown(0)

At:

countDown(0)

the base case executes:

return;

Then previous method calls complete one by one।

Recursion and the Call Stack

When a method calls another method, Java needs to remember:

Which method is active?
What arguments does it have?
Where should execution return?
What local variables belong to that invocation?

This information is associated with the call stack।

For:

countDown(
        3
);

the active calls conceptually become:

Top
↓
countDown(0)
countDown(1)
countDown(2)
countDown(3)
main()

Then they finish in reverse order।

Going Down and Coming Back Up

Consider:

static void show(
        int number
) {
    if (
            number == 0
    ) {
        return;
    }

    System.out.println(
            "Before: "
            + number
    );

    show(
            number - 1
    );

    System.out.println(
            "After: "
            + number
    );
}

Call:

show(
        3
);

Output:

Before: 3
Before: 2
Before: 1
After: 1
After: 2
After: 3

Why Does the Order Reverse?

Execution:

show(3)
    print Before 3

    show(2)
        print Before 2

        show(1)
            print Before 1

            show(0)
                return

            print After 1

        print After 2

    print After 3

Each call waits for the deeper call to finish before continuing।

This is one of the most important ideas in recursion।

Recursion Is Not Just Repetition

A loop repeats statements in one method invocation।

Recursion creates multiple method invocations।

Compare:

for (
        int i = 3;
        i >= 1;
        i--
) {
    System.out.println(
            i
    );
}

with:

static void countDown(
        int number
) {
    if (
            number == 0
    ) {
        return;
    }

    System.out.println(
            number
    );

    countDown(
            number - 1
    );
}

Both can produce similar output, but their execution models are different।

Every Recursive Call Needs Progress

This is critical।

Correct:

countDown(
        number - 1
);

The input moves toward:

Incorrect:

countDown(
        number
);

The input never changes।

Therefore the base case may never be reached।

Infinite Recursion

Example:

static void greet() {
    System.out.println(
            "Hello"
    );

    greet();
}

There is no base case।

This method keeps calling itself।

Eventually Java cannot allocate another call stack frame and fails।

`StackOverflowError`

Infinite or excessively deep recursion can cause:

StackOverflowError

Example:

static void forever(
        int number
) {
    forever(
            number + 1
    );
}

Eventually:

java.lang.StackOverflowError

may occur।

This is an Error, not a normal exception you should use as part of application control flow।

The fix is usually:

Correct the recursion design

not:

Catch StackOverflowError

Three Questions for Recursive Methods

When writing recursion, ask:

1. What is the smallest problem I can solve directly?
2. How do I reduce the current problem?
3. Does every recursive path eventually reach the base case?

If the third answer is unclear, the recursion is unsafe।

Factorial

A classic recursive example is factorial।

For a positive integer:

5! = 5 × 4 × 3 × 2 × 1

Result:

Mathematically:

n! = n × (n - 1)!

with base case:

0! = 1

Recursive Factorial

static long factorial(
        int number
) {
    if (
            number < 0
    ) {
        throw new IllegalArgumentException(
                "Number cannot be negative."
        );
    }

    if (
            number == 0
    ) {
        return 1;
    }

    return number
            * factorial(
                    number - 1
            );
}

Trace `factorial(4)`

Start:

factorial(4)

becomes:

4 × factorial(3)

then:

4 × 3 × factorial(2)

then:

4 × 3 × 2 × factorial(1)

then:

4 × 3 × 2 × 1 × factorial(0)

base case:

factorial(0) = 1

Then values return upward:

factorial(1) = 1 × 1 = 1

factorial(2) = 2 × 1 = 2

factorial(3) = 3 × 2 = 6

factorial(4) = 4 × 6 = 24

Recursive Return Values

Recursion does not have to be void।

A recursive method can wait for another invocation and use its returned value।

Example:

return number
        * factorial(
                number - 1
        );

The current call depends on the result of the smaller call।

Sum from 1 to N

We want:

sum(5)

to calculate:

1 + 2 + 3 + 4 + 5

Result:

Recursive relationship:

sum(n) = n + sum(n - 1)

Base case:

sum(0) = 0

Implementation

static int sumTo(
        int number
) {
    if (
            number < 0
    ) {
        throw new IllegalArgumentException(
                "Number cannot be negative."
        );
    }

    if (
            number == 0
    ) {
        return 0;
    }

    return number
            + sumTo(
                    number - 1
            );
}

Trace `sumTo(3)`

sumTo(3)
= 3 + sumTo(2)

= 3 + 2 + sumTo(1)

= 3 + 2 + 1 + sumTo(0)

= 3 + 2 + 1 + 0

= 6

Iterative Equivalent

The same task can be written with a loop:

static int sumTo(
        int number
) {
    if (
            number < 0
    ) {
        throw new IllegalArgumentException(
                "Number cannot be negative."
        );
    }

    int total =
            0;

    for (
            int i = 1;
            i <= number;
            i++
    ) {
        total +=
                i;
    }

    return total;
}

For this problem, the loop is arguably simpler।

This is important:

Just because recursion is possible
does not mean recursion is better.

Recursively Print Numbers Upward

Suppose we want:

but the recursive input begins at 5।

We can move the print statement after the recursive call।

static void printUpTo(
        int number
) {
    if (
            number == 0
    ) {
        return;
    }

    printUpTo(
            number - 1
    );

    System.out.println(
            number
    );
}

Call:

printUpTo(
        5
);

Output:

Why Does This Work?

Calls go downward:

5 → 4 → 3 → 2 → 1 → 0

Printing happens while calls return:

1 → 2 → 3 → 4 → 5

This ability to perform work:

before recursion

or:

after recursion

is extremely useful in tree algorithms later।

Recursively Processing an Array

Suppose:

int[] numbers = {
        10,
        20,
        30
};

We can recursively print from an index।

static void print(
        int[] numbers,
        int index
) {
    if (
            index == numbers.length
    ) {
        return;
    }

    System.out.println(
            numbers[index]
    );

    print(
            numbers,
            index + 1
    );
}

Call:

print(
        numbers,
        0
);

Base Case for Array Traversal

index == numbers.length

means:

No more valid elements remain.

Recursive progress:

index + 1

moves toward the stopping condition।

Recursive Array Sum

static int sum(
        int[] numbers,
        int index
) {
    if (
            index == numbers.length
    ) {
        return 0;
    }

    return numbers[index]
            + sum(
                    numbers,
                    index + 1
            );
}

Usage:

int result =
        sum(
                numbers,
                0
        );

Trace the Array Sum

For:

[10, 20, 30]

we get:

sum(numbers, 0)
= 10 + sum(numbers, 1)

= 10 + 20 + sum(numbers, 2)

= 10 + 20 + 30 + sum(numbers, 3)

= 10 + 20 + 30 + 0

= 60

Hide the Starting Index

A public API like:

sum(
        numbers,
        0
);

exposes an internal implementation detail:

Starting index

We can wrap it:

static int sum(
        int[] numbers
) {
    return sum(
            numbers,
            0
    );
}

static int sum(
        int[] numbers,
        int index
) {
    if (
            index == numbers.length
    ) {
        return 0;
    }

    return numbers[index]
            + sum(
                    numbers,
                    index + 1
            );
}

Caller now uses:

sum(
        numbers
);

This is a cleaner method interface।

Recursive Search

We can also search recursively।

static boolean contains(
        int[] numbers,
        int target
) {
    return contains(
            numbers,
            target,
            0
    );
}

static boolean contains(
        int[] numbers,
        int target,
        int index
) {
    if (
            index == numbers.length
    ) {
        return false;
    }

    if (
            numbers[index] == target
    ) {
        return true;
    }

    return contains(
            numbers,
            target,
            index + 1
    );
}

Two Base-Like Outcomes

Notice recursive methods can have multiple stopping outcomes।

For search:

Reached end
→ false

or:

Found target
→ true

Not every recursive method has exactly one if base case।

What matters is:

All valid execution paths eventually stop.

Recursive String Processing

Suppose we want to print the characters of a string one by one।

static void printCharacters(
        String value,
        int index
) {
    if (
            index == value.length()
    ) {
        return;
    }

    System.out.println(
            value.charAt(
                    index
            )
    );

    printCharacters(
            value,
            index + 1
    );
}

Reverse a String Recursively

We can build a reversed string:

static String reverse(
        String value
) {
    if (
            value.length() <= 1
    ) {
        return value;
    }

    return reverse(
            value.substring(
                    1
            )
    )
            + value.charAt(
                    0
            );
}

For:

Java

conceptually:

reverse("Java")
= reverse("ava") + "J"

= reverse("va") + "a" + "J"

= reverse("a") + "v" + "a" + "J"

= "a" + "v" + "a" + "J"

= "avaJ"

Is This the Best Production String Reverse?

Not necessarily।

Repeated string creation and substring() operations may make this less efficient and less obvious than using an iterative approach or StringBuilder।

It is useful here because it demonstrates recursive decomposition।

The goal is understanding recursion, not recommending recursion for every string operation।

Fibonacci: A Famous but Dangerous Example

The Fibonacci sequence begins:

Definition:

fib(0) = 0
fib(1) = 1

fib(n) = fib(n - 1) + fib(n - 2)

Naive recursive implementation:

static long fibonacci(
        int number
) {
    if (
            number < 0
    ) {
        throw new IllegalArgumentException(
                "Number cannot be negative."
        );
    }

    if (
            number <= 1
    ) {
        return number;
    }

    return fibonacci(
            number - 1
    )
            + fibonacci(
                    number - 2
            );
}

Why This Example Can Be Misleading

It is mathematically elegant but computationally inefficient।

For:

fibonacci(
        5
);

the program repeatedly recalculates the same values।

Conceptually:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   └── fib(1)
│   └── fib(2)
└── fib(3)
    ├── fib(2)
    └── fib(1)

Notice:

fib(3)
fib(2)

are calculated multiple times।

Iterative Fibonacci

For a simple Fibonacci calculation, iteration is usually much more efficient:

static long fibonacci(
        int number
) {
    if (
            number < 0
    ) {
        throw new IllegalArgumentException(
                "Number cannot be negative."
        );
    }

    if (
            number <= 1
    ) {
        return number;
    }

    long previous =
            0;

    long current =
            1;

    for (
            int i = 2;
            i <= number;
            i++
    ) {
        long next =
                previous
                + current;

        previous =
                current;

        current =
                next;
    }

    return current;
}

Later, in algorithms, we will talk about why the naive recursive version has poor complexity।

Direct Recursion

A method directly calls itself:

static void method() {
    method();
}

This is:

Direct recursion

Indirect Recursion

A method may call another method that eventually calls the first one।

Example:

static void first(
        int value
) {
    if (
            value == 0
    ) {
        return;
    }

    second(
            value - 1
    );
}

static void second(
        int value
) {
    if (
            value == 0
    ) {
        return;
    }

    first(
            value - 1
    );
}

This is:

Indirect recursion

It exists, but direct recursion is easier to reason about and more common in beginner examples।

Recursive State Lives in Each Call

Consider:

static void show(
        int number
) {
    int doubled =
            number * 2;

    if (
            number == 0
    ) {
        return;
    }

    show(
            number - 1
    );

    System.out.println(
            doubled
    );
}

Every invocation has its own:

number
doubled

values।

Example calls:

show(3) → doubled = 6
show(2) → doubled = 4
show(1) → doubled = 2

These local values remain associated with their respective active calls until each returns।

Recursion Depth

Recursion depth means roughly:

How many recursive calls are active at once?

For:

countDown(
        5
);

depth is small।

For:

countDown(
        10_000_000
);

the recursion will likely fail long before reaching zero because too many stack frames are required।

Java Does Not Guarantee Tail Call Optimization

Some languages optimize certain recursive calls so they do not consume additional stack space।

Java does not generally guarantee tail call optimization।

Therefore even a recursion where the recursive call is the final action can still consume one stack frame per call।

Example:

static void countDown(
        int number
) {
    if (
            number == 0
    ) {
        return;
    }

    countDown(
            number - 1
    );
}

Do not assume this can recurse indefinitely।

Recursion vs Iteration

Both can express repeated work।

Iteration

for
while
do-while

usually uses a loop variable and repeats inside one method invocation।

Recursion

A method repeatedly calls itself with smaller subproblems।

When a Loop Is Usually Better

Prefer iteration for straightforward sequential repetition such as:

Print numbers 1–100
Sum an array
Count values
Process every item
Simple linear search

Loops usually have:

Less stack usage
Straightforward performance
Simple execution flow

When Recursion Can Be Natural

Recursion becomes especially useful when data or problems are recursively structured।

Examples:

Trees
Directory hierarchies
Nested expressions
Divide-and-conquer algorithms
Depth-first search
Backtracking

We will see this later with algorithms such as:

Merge Sort
Quick Sort
Tree traversal

Tree-Like Thinking

Imagine a folder:

projects/
├── java/
│   ├── src/
│   └── docs/
└── backend/
    ├── api/
    └── database/

A directory can contain:

Files
Other directories

Those directories may contain more directories।

This naturally recursive structure often fits recursive traversal।

Divide and Conquer

Some algorithms solve a problem by:

Divide into smaller subproblems
Solve those subproblems
Combine the results

Example:

Merge Sort

Recursion often expresses this structure clearly।

We'll study it in the Algorithms module।

Recursive Thinking Process

Suppose the problem is:

Calculate factorial(n)

Instead of asking:

How do I calculate the entire answer immediately?

Ask:

If I already knew factorial(n - 1), how would I calculate factorial(n)?

Answer:

n × factorial(n - 1)

Then ask:

What smallest input can I solve immediately?

Answer:

factorial(0) = 1

That gives both recursive parts।

Another Recursive Thinking Example

Problem:

Sum array starting at index

Ask:

If I already knew the sum of everything after this element, what remains?

Answer:

current element + remaining sum

So:

numbers[index]
+ sum(
        numbers,
        index + 1
)

Base case:

index == numbers.length

then remaining sum is:

Avoid Changing the Problem Without Progress

Bad:

static int sum(
        int number
) {
    if (
            number == 0
    ) {
        return 0;
    }

    return number
            + sum(
                    number
            );
}

The recursive call uses the same input।

So:

sum(5)
→ sum(5)
→ sum(5)
→ ...

The base case is never reached।

Correct:

sum(
        number - 1
);

Base Case Must Match the Direction

Suppose:

static void countUp(
        int number
) {
    if (
            number == 10
    ) {
        return;
    }

    countUp(
            number + 1
    );
}

Call:

countUp(
        0
);

eventually reaches 10।

But calling:

countUp(
        20
);

keeps increasing:

20
21
22
...

and never reaches 10।

The input contract must be compatible with the recursive direction।

Better Boundary Design

We could explicitly reject unsupported values:

static void countUp(
        int number
) {
    if (
            number > 10
    ) {
        throw new IllegalArgumentException(
                "Number cannot be greater than 10."
        );
    }

    if (
            number == 10
    ) {
        return;
    }

    countUp(
            number + 1
    );
}

This makes the method's assumptions clearer।

Common Beginner Mistake 1: No Base Case

Bad:

static void print(
        int number
) {
    System.out.println(
            number
    );

    print(
            number - 1
    );
}

There is no stopping condition।

Common Beginner Mistake 2: Input Does Not Move Toward Base Case

Bad:

static void print(
        int number
) {
    if (
            number == 0
    ) {
        return;
    }

    print(
            number + 1
    );
}

For positive input, it moves away from zero।

Common Beginner Mistake 3: Wrong Base Result

Factorial base case:

if (
        number == 0
) {
    return 0;
}

would be wrong।

Because:

0! = 1

and multiplication by zero would make every higher factorial zero।

Correct:

return 1;

Base-case result must preserve the recursive relationship correctly।

Common Beginner Mistake 4: Confusing Call Order and Return Order

Calls happen:

but code after the recursive call executes:

1
2
3

Tracing both directions is essential।

Common Beginner Mistake 5: Using Recursion for Everything

This:

sum array recursively

is useful for learning recursion।

But a loop:

for (
        int value
        : values
)

is often simpler in production for linear traversal।

Choose the simpler structure unless recursion matches the problem naturally।

Common Beginner Mistake 6: Ignoring Stack Depth

A method may be logically correct but unsafe for huge input sizes։

Example:

countDown(
        1_000_000
);

may exhaust the stack։

Correctness includes operational behavior, not just mathematical output।

Common Beginner Mistake 7: Naive Recursive Fibonacci

The naive implementation is elegant but repeats huge amounts of work।

It is useful for understanding recursion trees, not as the default production implementation।

Practical Example: Recursive Power

We want:

power(2, 4)

to calculate:

2 × 2 × 2 × 2 = 16

Recursive relationship:

base^exponent
=
base × base^(exponent - 1)

Base case:

exponent = 0
→ 1

Implementation

static long power(
        int base,
        int exponent
) {
    if (
            exponent < 0
    ) {
        throw new IllegalArgumentException(
                "Exponent cannot be negative."
        );
    }

    if (
            exponent == 0
    ) {
        return 1;
    }

    return base
            * power(
                    base,
                    exponent - 1
            );
}

Trace `power(2, 3)`

power(2, 3)
= 2 × power(2, 2)

= 2 × 2 × power(2, 1)

= 2 × 2 × 2 × power(2, 0)

= 2 × 2 × 2 × 1

= 8

Practical Example: Count Occurrences Recursively

static int countOccurrences(
        int[] numbers,
        int target
) {
    return countOccurrences(
            numbers,
            target,
            0
    );
}

static int countOccurrences(
        int[] numbers,
        int target,
        int index
) {
    if (
            index == numbers.length
    ) {
        return 0;
    }

    int currentMatch =
            numbers[index] == target
                    ? 1
                    : 0;

    return currentMatch
            + countOccurrences(
                    numbers,
                    target,
                    index + 1
            );
}

For:

[2, 3, 2, 5, 2]

target:

result:

Practical Example: Find Maximum Recursively

static int max(
        int[] numbers
) {
    if (
            numbers.length == 0
    ) {
        throw new IllegalArgumentException(
                "Array cannot be empty."
        );
    }

    return max(
            numbers,
            1,
            numbers[0]
    );
}

static int max(
        int[] numbers,
        int index,
        int currentMax
) {
    if (
            index == numbers.length
    ) {
        return currentMax;
    }

    int nextMax =
            numbers[index] > currentMax
                    ? numbers[index]
                    : currentMax;

    return max(
            numbers,
            index + 1,
            nextMax
    );
}

This demonstrates carrying state through recursive parameters।

Recursive Parameters as State

In:

max(
        numbers,
        index,
        currentMax
)

the recursive call receives updated state:

Next index
Current best value

This is conceptually similar to variables updated in a loop।

Iteration:

for (...) {
    currentMax = ...
}

Recursion:

max(
        ...,
        nextIndex,
        nextMax
);

Practice 1: Countdown

Write:

static void countDown(
        int number
)

that prints from number down to 1।

Solution

static void countDown(
        int number
) {
    if (
            number <= 0
    ) {
        return;
    }

    System.out.println(
            number
    );

    countDown(
            number - 1
    );
}

Practice 2: Print Upward

Write a recursive method that receives 5 and prints:

Solution

static void printUpTo(
        int number
) {
    if (
            number <= 0
    ) {
        return;
    }

    printUpTo(
            number - 1
    );

    System.out.println(
            number
    );
}

Practice 3: Factorial

Calculate:

6!

using recursion।

Solution

static long factorial(
        int number
) {
    if (
            number < 0
    ) {
        throw new IllegalArgumentException(
                "Number cannot be negative."
        );
    }

    if (
            number == 0
    ) {
        return 1;
    }

    return number
            * factorial(
                    number - 1
            );
}

Result:

Practice 4: Recursive Array Sum

Write:

static int sum(
        int[] numbers
)

using recursion।

Solution

static int sum(
        int[] numbers
) {
    return sum(
            numbers,
            0
    );
}

static int sum(
        int[] numbers,
        int index
) {
    if (
            index == numbers.length
    ) {
        return 0;
    }

    return numbers[index]
            + sum(
                    numbers,
                    index + 1
            );
}

Practice 5: Recursive Contains

Implement:

static boolean contains(
        String[] values,
        String target
)

using recursion।

Solution

static boolean contains(
        String[] values,
        String target
) {
    return contains(
            values,
            target,
            0
    );
}

static boolean contains(
        String[] values,
        String target,
        int index
) {
    if (
            index == values.length
    ) {
        return false;
    }

    if (
            values[index].equals(
                    target
            )
    ) {
        return true;
    }

    return contains(
            values,
            target,
            index + 1
    );
}

Practice 6: Predict the Output

static void show(
        int number
) {
    if (
            number == 0
    ) {
        return;
    }

    System.out.print(
            number
            + " "
    );

    show(
            number - 1
    );
}

Call:

show(
        3
);

Answer

3 2 1

Practice 7: Predict the Output

static void show(
        int number
) {
    if (
            number == 0
    ) {
        return;
    }

    show(
            number - 1
    );

    System.out.print(
            number
            + " "
    );
}

Call:

show(
        3
);

Answer

1 2 3

The print happens while calls return।

Practice 8: Find the Bug

static int sum(
        int number
) {
    if (
            number == 0
    ) {
        return 0;
    }

    return number
            + sum(
                    number
            );
}

Answer

The recursive call receives the same value:

sum(
        number
);

so the method does not progress toward the base case।

Correct:

sum(
        number - 1
);

Practice 9: Find the Bug

static long factorial(
        int number
) {
    if (
            number == 0
    ) {
        return 0;
    }

    return number
            * factorial(
                    number - 1
            );
}

Answer

The base result is wrong।

It should be:

return 1;

because:

0! = 1

Practice 10: Recursion or Loop?

Which would you normally prefer for printing every element of a large array?

Answer

Usually a loop:

for

or enhanced for।

It is simpler and avoids unnecessary stack growth।

True or False

Recursion means a method may call itself.
Every recursive algorithm needs some stopping condition.
A base case should normally reduce the problem further.
Recursive calls create additional method invocations.
Code after a recursive call executes before the deeper call.
Incorrect recursion can cause StackOverflowError.
Java guarantees tail-call optimization.
Every loop should be replaced with recursion.
Tree traversal is a natural use case for recursion.
A recursive method may return values.
Recursive calls should usually move toward a base case.
Naive recursive Fibonacci repeats computations.

Answers

1. True
2. True
3. False
4. True
5. False
6. True
7. False
8. False
9. True
10. True
11. True
12. True

Knowledge Check

Question 1

What is recursion?

Question 2

What is a base case?

Question 3

What is the recursive case?

Question 4

Why must recursive input usually become smaller or simpler?

Question 5

What happens to the current method call while a deeper recursive call executes?

Question 6

What is StackOverflowError in the context of recursion?

Question 7

Why is factorial(0) equal to 1 important for the recursive implementation?

Question 8

Why can code after a recursive call execute in reverse order?

Question 9

Why is recursion often natural for trees?

Question 10

Why might a loop be preferable for simple linear array traversal?

Question 11

Does Java guarantee tail-recursion optimization?

Question 12

What three questions should you ask when designing recursion?

Knowledge Check Answers

Answer 1

Recursion is a technique where a method solves a problem by invoking itself, directly or indirectly, with a smaller or simpler version of that problem।

Answer 2

A base case is a condition that can be solved directly and stops further recursive calls।

Answer 3

The recursive case reduces the current problem and calls the method again using that reduced input।

Answer 4

So execution eventually reaches a stopping condition rather than recursing forever।

Answer 5

Its execution state remains active on the call stack and resumes after the deeper call returns।

Answer 6

It is a runtime failure that can occur when too many nested method calls exhaust available stack space।

Answer 7

It provides the correct stopping value for multiplication; returning 0 would make every higher factorial result zero।

Answer 8

Each method invocation waits for its deeper call to complete, so the deepest call finishes first and control returns upward through earlier invocations।

Answer 9

A tree node may contain child nodes that are themselves roots of smaller trees, matching recursive problem structure naturally।

Answer 10

A loop is generally simpler, uses constant call-stack depth, and directly expresses sequential repetition।

Answer 11

No. Java does not generally guarantee tail-call optimization।

Answer 12

Ask:

What is the base case?

How do I reduce the problem?

Will every recursive path eventually reach the base case?

Lesson Summary

এই lesson-এ আমরা recursion-এর foundation শিখেছি।

We learned:

Recursion means a method calls itself directly or indirectly
Recursive solutions normally contain a base case and recursive case
The base case stops further calls
Recursive input should move toward the base case
Every recursive invocation has its own parameters and local state
Active recursive calls build up on the call stack
Calls descend first and return in reverse order
Code before and after a recursive call can produce very different execution orders
Recursive methods can return values
Factorial and summation demonstrate recursive decomposition
Arrays can be traversed recursively using an index
Helper overloads can hide recursion-specific parameters from callers
Search can terminate recursively as soon as a match is found
Infinite or excessively deep recursion can cause StackOverflowError
Java does not guarantee tail-call optimization
Recursion can be elegant for recursively structured problems
Simple sequential tasks are often better expressed with loops
Naive recursion can repeat work and become inefficient
Trees, divide-and-conquer algorithms, directory traversal, and backtracking are important future use cases

The core recursive model is:

Solve the smallest case directly.

For every larger case:
reduce it to a smaller version
of the same problem.

Recursion is not a replacement for loops।

It is another problem-solving tool, especially useful when the structure of the problem itself is recursive।

Next Lesson

পরবর্তী lesson:

Module Practice and Assessment

আমরা Module 2-এর সব topics একসঙ্গে practice করব:

Methods
Parameters and return values
Scope
static
Method overloading
Arrays
Array traversal
2D and multidimensional arrays
java.util.Arrays
Recursion
Debugging exercises
Small implementation challenges
Module-wide assessment

Lesson Overview

What Is Recursion?

Base Case

Recursive Case

First Recursive Example

Trace the Calls

Recursion and the Call Stack

Going Down and Coming Back Up

Why Does the Order Reverse?

Recursion Is Not Just Repetition

Every Recursive Call Needs Progress

Infinite Recursion

StackOverflowError

Three Questions for Recursive Methods

Factorial

Recursive Factorial

Trace factorial(4)

Recursive Return Values

Sum from 1 to N

Implementation

Trace sumTo(3)

Iterative Equivalent

Recursively Print Numbers Upward

Why Does This Work?

Recursively Processing an Array

Base Case for Array Traversal

Recursive Array Sum

Trace the Array Sum

Hide the Starting Index

Recursive Search

Two Base-Like Outcomes

Recursive String Processing

Reverse a String Recursively

Is This the Best Production String Reverse?

Fibonacci: A Famous but Dangerous Example

Why This Example Can Be Misleading

Iterative Fibonacci

Direct Recursion

Indirect Recursion

Recursive State Lives in Each Call

Recursion Depth

Java Does Not Guarantee Tail Call Optimization

Recursion vs Iteration

Iteration

Recursion

When a Loop Is Usually Better

When Recursion Can Be Natural

Tree-Like Thinking

Divide and Conquer

Recursive Thinking Process

Another Recursive Thinking Example

Avoid Changing the Problem Without Progress

Base Case Must Match the Direction

Better Boundary Design

Common Beginner Mistake 1: No Base Case

Common Beginner Mistake 2: Input Does Not Move Toward Base Case

Common Beginner Mistake 3: Wrong Base Result

Common Beginner Mistake 4: Confusing Call Order and Return Order

Common Beginner Mistake 5: Using Recursion for Everything

Common Beginner Mistake 6: Ignoring Stack Depth

Common Beginner Mistake 7: Naive Recursive Fibonacci

Practical Example: Recursive Power

Implementation

Trace power(2, 3)

Practical Example: Count Occurrences Recursively

Practical Example: Find Maximum Recursively

Recursive Parameters as State

Practice 1: Countdown

Solution

Practice 2: Print Upward

Solution

Practice 3: Factorial

Solution

Practice 4: Recursive Array Sum

Solution

Practice 5: Recursive Contains

Solution

Practice 6: Predict the Output

Answer

Practice 7: Predict the Output

`StackOverflowError`

Trace `factorial(4)`

Trace `sumTo(3)`

Trace `power(2, 3)`