Data Structures

Principle of Mathematical
Induction
1. What is Mathematical Induction?
Mathematical Induction is a proof technique used to prove statements or formulas that are true for all
natural numbers (n ∈ ℕ) starting from some base case.

2. The Concept: Mathematical Induction

Mathematical induction is like a line of falling dominoes. If you can prove the first one falls (Base Case)
and that if any one falls, the next one must also fall (Inductive Step), then you've proven the whole line
falls.

Domino effect:
 If the first domino falls (base case is true),
 and each domino knocks down the next one (inductive step),
 then all dominos will eventually fall (statement true for all n).
Steps of Mathematical Induction :

To prove a statement P(n) is true for all integers n≥k :

1. Base Case (Initialization):

Show that P(k) is true. (Usually k=0 or k=1)

2. Inductive Hypothesis:
Assume that P(m) is true for some arbitrary m≥k.

3. Inductive Step:
Prove that if P(m) is true, then P(m+1) is also true. If both steps hold, then P(n) is true for all n≥k.
 3. Example Proof using Induction
Statement (P(n)): 1+2+3+...+n=n(n+1)/2
•Base Case (n=1):
LHS = 1, RHS = (1×2)/2 = 1

•Inductive Hypothesis:
Assume for n=m
1+2+...+m = m(m+1)/2

•Inductive Step (n = m+1): The Goal: Prove it works for (m+1). We want to reach the target:
Add (m+1) to both sides: (m+1)(m+2) /2.

m(m+1)
1+2+...+m+(m+1)= ------------- + (m+1)
2
Simplify:The Common Denominator (Simplification):

=m(m+1)+2(m+1) (m+1)(m+2)
----------------------- = ----------------
2 2
Which matches RHS for n = m+1.
Factoring: Notice both terms in the top have (m+1). Pull it out: Thus, statement is true for all n ≥ 1.
Example :1 (Using Induction Idea)

import [Link]; [Link]("Sum using formula = " + formula);

public class Main { [Link]("Sum using recursion = " + recursiveSum);
// Function to compute sum of first n natural numbers
public static int sumNum(int n) { if (formula == recursiveSum) {
if (n == 1) { [Link]("Proved using induction idea !!!!");
return 1; // Base Case } else {
} [Link]("Mismatch found!");
return n + sumNum(n - 1); // Recursive Step }
} [Link]();
}
public static void main(String[] args) { }
Scanner scanner = new Scanner([Link]);

[Link]("Enter n: "); Output

int n = [Link](); Enter n: 5
Sum using formula = 15
// Formula based result Sum using recursion = 15
int formula = n * (n + 1) / 2; Proved using induction idea !!!!
// Recursive result (induction-like proof in code)
int recursiveSum = sumNum(n);
Real-World Usage of Induction

Mathematical induction is widely used in computer science & C++ programming:

 Algorithm correctness proofs (proving recursive algorithms are correct).
 Loop invariants (ensuring correctness of iterative programs).
 Data structures (properties of trees, graphs).
 Complexity analysis (proving runtime formulas).
 Mathematical formula validation (like summations, series).

Example in Real Life:

 Recursive programs: To prove a recursive factorial function always gives correct output for all n.
 Network growth: Proving number of connections in a fully connected network = n(n-1)/2.
 Savings calculation: Proving the formula for total money saved if you save an increasing amount daily.

 PMI is like a chain reaction.

 Used in mathematics, algorithms, recursion, correctness proofs.
 In Java, recursive functions are direct representations of induction logic.
Recursion
What is Recursion?
Recursion is a programming technique where a function calls itself to solve a smaller sub problem
of the original bigger problem.

Key Concepts:
 Base Case: Stops the recursion (factorial(0) = 1)
 Recursive Case: Keeps breaking the problem into smaller sub problems
 Call Stack: Each recursive call is stored on the call stack until the base case is reached

Basic structure:
void function() {
if (base_condition) return;
function(); // recursive call
}
Why use Recursion?

Recursion is especially useful for problems that can be broken down into similar sub
problems, like:

 Ideal for Tree/Graph traversal

 Backtracking problems (e.g., Sudoku, N-Queens)
 Divide-and-conquer algorithms (e.g., Merge Sort, Quick Sort)
 Mathematical problems (e.g., factorial, Fibonacci, GCD) algorithms. Saves time
in mathematical or pattern-based logic.
 Simplifies code for problems with repetitive patterns.
Advantages of Recursion
 Cleaner and shorter code for problems with repeated substructure
 Matches mathematical definitions (e.g., factorial, Fibonacci)
 Easier to conceptualize for tree and graph traversals

Disadvantages
 High memory usage (due to stack frames)
 Can lead to stack overflow if base case isn’t reached
 Generally slower than iterative solutions (due to function call overhead)
1. Factorial using Recursion

Formula: n! = n × (n - 1)!, with 0! = 1 (base case)

Example: 5! = 5 × 4 × 3 × 2 × 1 = 120

public class Main {

public static void main(String[] args) {

int num = 5;
[Link]("Factorial of %d is %d\n", num, factorial(num));
}

// Method to compute factorial recursively

public static int factorial(int n) {
if (n == 0) // base case
return 1;
else Output:
return n * factorial(n - 1); // recursive call Factorial of 5 is 120
}
}
Recursion Flow (Call Stack)

factorial(5)
↳ 5 × factorial(4)
↳ 4 × factorial(3)
↳ 3 × factorial(2)
↳ 2 × factorial(1)
↳ 1 × factorial(0)
↳ 1 ← base case returns
←1×1=1
←2×1=2
←3×2=6
← 4 × 6 = 24
← 5 × 24 = 120
Visual Diagram of Stack (Top-Down)

Usage:
|------------------------------|
 Used in mathematics (combinatorics, permutations, probability.).
| return 1 (factorial(0)) |
 Useful for solving problems involving sequences.
|------------------------------|
| 1 × factorial(0) = 1 |
|------------------------------|
| 2 × factorial(1) = 2 |
|------------------------------|
| 3 × factorial(2) = 6 |
|------------------------------|
| 4 × factorial(3) = 24 |
|------------------------------|
| 5 × factorial(4) = 120 |
|------------------------------|

At the bottom, the base case returns 1.

Then, each function "resumes" its execution by multiplying and returning the value to the previous caller.
Key Memory Concept: The Stack

In Java, each of these "Levels" occupies space in the Stack Memory.

 If you tried to calculate factorial(1000000), you would likely get a StackOverflowError because
the computer runs out of physical memory to keep track of all those "waiting" calls.

 The base case is essentially the "emergency brake" that stops the stack from growing forever.
2. Fibonacci Numbers Series Using Recursion
public class Main {

public static int fibonacci(int n) {

if (n == 0)
return 0;
else if (n == 1)
return 1; Output: 0 1 1 2 3 5 8
else
return fibonacci(n - 1) + fibonacci(n - 2);
}

public static void main(String[] args) {

// Fibonacci Execution
int i, fibLimit = 7;
[Link]("Fibonacci sequence: "); Usage: Used in finance, biological systems, data structure
for (i = 0; i < fibLimit; i++) { algorithms (e.g., trees, heaps).
[Link]("%d ", fibonacci(i));
}
[Link]();
}
}
3. Sum of Digits Using Recursion
Usage: Used in checksum algorithms, digit-based logic,
public class Main { numerology.

// Method to calculate the sum of digits recursively

public static int sumOfDigits(int n) { Output:
// Base case: if the number becomes 0, return 0 Sum of digits of 1234 is 10
if (n == 0) {
return 0;
} else {
// Recursive call: last digit (n % 10) + sum of remaining digits (n / 10)
return n % 10 + sumOfDigits(n / 10);
}
}

public static void main(String[] args) {

int number = 1234;
// Output result using formatted print
int result = sumOfDigits(number);
[Link]("Sum of digits of %d is %d\n", number, result);
}
}
4. Power of a Number (xⁿ) using Recursion
public class Main { Usage: Used in scientific calculators,
// Method to calculate power recursively encryption algorithms, exponential growth
public static int power(int base, int exponent) { calculations.
// Base case: if exponent is 0, return 1
if (exponent == 0) {
return 1;
}
// Recursive step: multiply base by power(base, exponent - 1)
return base * power(base, exponent - 1);
}

public static void main(String[] args) {

int base = 2;
int exp = 4;
Output:
2^4 = 16
// Output result using formatted print
int result = power(base, exp);
[Link]("%d^%d = %d\n", base, exp, result);
}
}
5. Reverse a String using Recursion
public static void main(String[] args) {
public class Main { // In Java, we convert the String to a char array to allow
// Method to reverse a character array recursively swapping
String input = "hello";
public static void reverse(char[] str, int start, int end) { char[] charArray = [Link]();
// Base case: if start index meets or exceeds end index, stop
if (start >= end) { // Call the recursive function (indices 0 to 4 for "hello")
return; reverse(charArray, 0, [Link] - 1);
}
// Convert back to string and print
// Swap characters using a temporary variable [Link]("Reversed string: ");
char temp = str[start]; [Link](new String(charArray));
str[start] = str[end]; }
str[end] = temp; }

// Recursive call: move indices toward the middle

reverse(str, start + 1, end - 1);
} Output:
Reversed string: olleh

Usage: Useful in string manipulation, compiler design, data parsing.

Recursion using Arrays
Program :1 Recursion using Arrays : Sum of Elements

The Goal: Calculate the total sum of an array without using a for loop.
The Logic: The sum of an array is the first element + the sum of the rest of the array.

public class SumArrayRecursive {

public static int sumArray(int[] arr, int size) {
[Link]("Winding: Entering sumArray for size " + size);
// Base Case Output:
if (size <= 0) { Winding: Entering sumArray for size 5
return 0; Winding: Entering sumArray for size 4
} Winding: Entering sumArray for size 3
// Recursive Step Winding: Entering sumArray for size 2
int result = arr[size - 1] + sumArray(arr, size - 1); Winding: Entering sumArray for size 1
[Link]("Unwinding: Returning " + result + " for size " + size); Winding: Entering sumArray for size 0
return result; Unwinding: Returning 1 for size 1
} Unwinding: Returning 3 for size 2
public static void main(String[] args) { Unwinding: Returning 6 for size 3
int[] data = {1, 2, 3, 4, 5}; Unwinding: Returning 10 for size 4
int n = [Link]; Unwinding: Returning 15 for size 5
[Link]("Sum of array: " + sumArray(data, n)); Sum of array: 15
}
}
How recursion works for this example?

When we call a recursive function, the computer doesn't finish the first call immediately. It "pauses" it and starts a new
one. This creates a Stack of Plates; you can’t get to the bottom plate until you remove all the ones on top. The Scenario
We are calling sumArray(arr, 3) where the array is {1, 2, 3}.

Phase 1: The "Winding" (Building the Stack)The computer keeps pushing new function calls onto the stack
because none of them have an answer yet. They are all "waiting.

Level Call Logic Status

Paused (Waiting for
Call 1 sumArray(3) 3 + sumArray(2)
Call 2)
Paused (Waiting for
Call 2 sumArray(2) 2 + sumArray(1)
Call 3)
Paused (Waiting for
Call 3 sumArray(1) 1 + sumArray(0)
Call 4)
Call 4 sumArray(0) return 0 Base Case Hit!
Phase 2: The "Unwinding" (Resolving the Returns)

Now that the Base Case returned 0, the stack begins to collapse from the top down. This is where the math actually
happens.

[Link] 4 finishes: It returns 0 to Call 3.

[Link] 3 resumes: It was waiting at 1 + sumArray(0). Now it has 1 + 0. It returns 1 to Call 2.
[Link] 2 resumes: It was waiting at 2 + sumArray(1). Now it has 2 + 1. It returns 3 to Call 1.
[Link] 1 resumes: It was waiting at 3 + sumArray(2). Now it has 3 + 3. It returns 6 to the main() function.

The "Stack Overflow" In coding : we 'll often hear about Stack Overflow.

 Imagine if you forgot the Base Case (the size <= 0 check).
 The computer would keep calling sumArray(-1), sumArray(-2), and so on.
 The "Stack of Plates" would get higher and higher until it hits the ceiling (the limit of your computer's
memory).
 Result: The program crashes because it ran out of room to "pause" more functions.
Recursion using Strings
Program :2 Recursion using Strings : Palindrome Check
The Goal: Check if a string reads the same forward and backward (e.g., "radar").
The Logic: Compare the first and last characters. If they match, strip them off and check the "inner" string.

public class PalindromeRecursive {

public static boolean isPalindrome(String str, int start, int end) {
// Print current comparison
[Link]("Checking: " + [Link](start) + " and " + [Link](end));
// Base Case 1: 0 or 1 character left
if (start >= end) {
return true;
}
// Base Case 2: Characters don't match
if ([Link](start) != [Link](end)) {
return false;
}
// Recursive Step
return isPalindrome(str, start + 1, end - 1);
}
 public static void main(String[] args) { Output:
String word = "racecar"; Checking: r and r
int len = [Link](); Checking: a and a
if (isPalindrome(word, 0, len - 1)) { Checking: c and c
[Link](word + " is a Palindrome"); Checking: e and e
} else { Checking: c and c
[Link](word + " is not a Palindrome"); Checking: a and a
} Checking: r and r
} racecar is a Palindrome
}
Recursion using 2D Arrays
Program :3 Recursion using 2D Arrays: Flood Fill
The Goal: In a grid (like a paint app), change the colour of a target pixel and all adjacent pixels of the same color. This is a foundational
"Graph" algorithm called DFS (Depth First Search).

public class FloodFill {

static final int ROWS = 3;
static final int COLS = 3;
public static void floodFill(int[][] screen, int x, int y, int oldColor, int newColor) {
// Base Case: Out of bounds or not matching old color
if (x < 0 || x >= ROWS || y < 0 || y >= COLS || screen[x][y] != oldColor) {
return;
}
// Change color
screen[x][y] = newColor;
// Recursive calls (Up, Down, Left, Right)
floodFill(screen, x + 1, y, oldColor, newColor);
floodFill(screen, x - 1, y, oldColor, newColor);
floodFill(screen, x, y + 1, oldColor, newColor);
floodFill(screen, x, y - 1, oldColor, newColor);
}
public static void main(String[] args) {
int[][] screen = { Output:
{1, 1, 0}, 220
{1, 1, 1}, 222
{0, 1, 0} 020
};
// Start at (1,1), change 1 → 2
floodFill(screen, 1, 1, 1, 2);
// Print result
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
[Link](screen[i][j] + " ");
}
[Link]();
}
}
}
The "Visualization": Tracing Flood Fill
Output:
Exploring Cell: (1, 1) Exploring Cell: (1, 0) Exploring Cell: (0, 2)
*** Painted (1, 1) with color 2 *** *** Painted (1, 0) with color 2 *** -> Hit wall or wrong color at (0, 2)
Exploring Cell: (2, 1) Exploring Cell: (2, 0) Exploring Cell: (1, 3)
*** Painted (2, 1) with color 2 *** -> Hit wall or wrong color at (2, 0) Exploring Cell: (1, 1)
Exploring Cell: (3, 1) Exploring Cell: (0, 0) -> Hit wall or wrong color at (1, 1)
Exploring Cell: (1, 1) -> Hit wall or wrong color at (0, 0) Exploring Cell: (1, 0)
-> Hit wall or wrong color at (1, 1) Exploring Cell: (1, 1) -> Hit wall or wrong color at (1, 0)
Exploring Cell: (2, 2) -> Hit wall or wrong color at (1, 1)
-> Hit wall or wrong color at (2, 2) Exploring Cell: (1, -1)
Exploring Cell: (2, 0) Exploring Cell: (-1, 0)
-> Hit wall or wrong color at (2, 0) Exploring Cell: (0, 1)
Exploring Cell: (0, 1) -> Hit wall or wrong color at (0, 1)
*** Painted (0, 1) with color 2 *** Exploring Cell: (0, -1)
Exploring Cell: (1, 1) Exploring Cell: (1, 2)
-> Hit wall or wrong color at (1, 1) *** Painted (1, 2) with color 2 ***
Exploring Cell: (-1, 1) Exploring Cell: (2, 2)
Exploring Cell: (0, 2) -> Hit wall or wrong color at (2, 2)
-> Hit wall or wrong color at (0, 2)
Exploring Cell: (0, 0)
*** Painted (0, 0) with color 2 ***
PROGRAMS
PROGRAM 1:
Imagine a determined young athlete named Alex who is training for a big competition. As part of his training, he
must climb a set of n stairs to reach the top of a training tower. Each time he practises, he can either take a
single step (climb 1 stair) or take a bigger leap (climb 2 stairs). Alex is curious about how many different ways
he can reach the top of the stairs based on his climbing patterns. Alex decides to record his attempts to find out
how many unique sequences of steps he takes to reach the top.

Task : Given an integer n representing the number of stairs, determine the number of distinct ways Alex can
reach the top.

Input Format : An integer n, the total number of stairs.

Output Format : Print the number of distinct ways to reach the top

Example 1: Example 3:
Input: n = 1 Output: 1 Input: n = 4 Output: 5
Explanation:
There is only one way to climb 1 stair. Explanation:
There are five ways to reach the 4th stair: {1, 1, 1, 1}, {1, 1, 2}, {2,
Example 2: 1, 1}, {1, 2, 1} and {2,2}.
Input: n = 2 Output: 2
Explanation:
There are two ways to reach the 2nd stair: {1, 1} and {2}.
Solution:
public class Main {
Output:
// Method to count ways to reach the top recursively Ways to climb 4 stairs: 5
public static int countWays(int n) {
// Base cases: If there are 0 or 1 stairs, there is only one way
if (n == 0 || n == 1) {
return 1;
}
// Recursive step: countWays(n-1) + countWays(n-2)
return countWays(n - 1) + countWays(n - 2);
}
public static void main(String[] args) {
int n = 4;
// Output the result
[Link]("Ways to climb " + n + " stairs: " + countWays(n));
}
}
How the Recursion Tree Works :

Because each call to countWays(n) triggers two more calls, the program creates a "tree" of operations. For n = 4,
the logic breaks down like this:

•countWays(4) splits into (3) and (2).

•countWays(3) splits into (2) and (1).

•The process continues until every branch hits the Base Case (0 or 1).
•Finally, the program adds up all the 1s returned from the base cases to get the total (which is 5 for n=4).
Solution:
results.push_back("{" + path + "}");
return;
#include <iostream>
}
#include <vector>
#include <string>
// Take 1 step if possible
if (n >= 1) {
using namespace std;
findPaths(n - 1, path + "1, ", results);
}
/**
* Helper function to find and print paths
// Take 2 steps if possible
* @param n: remaining stairs to climb
if (n >= 2) {
* @param path: the current sequence of steps taken
findPaths(n - 2, path + "2, ", results);
* @param results: a vector to store the final path strings
}
*/
}
void findPaths(int n, string path, vector<string>& results) {
// Base Case: We reached the top exactly
if (n == 0) {
// Remove the trailing comma and space for clean output
if (![Link]()) {
path = [Link](0, [Link]() - 2);
}
int main() {
int n = 4;
vector<string> results;

// Start recursion with an empty path

findPaths(n, "", results);

// Print the final summary

cout << "Input: n = " << n << " Output: " << [Link]() << endl;
cout << "There are " << [Link]() << " ways to reach the " << n << "th stair: ";

for (int i = 0; i < [Link](); i++) {

cout << results[i];
if (i < [Link]() - 1) {
cout << ", ";
Input: n = 4 Output: 5
}
There are 5 ways to reach the 4th stair: {1, 1, 1, 1}, {1, 1, 2}, {1,
}
2, 1}, {2, 1, 1}, {2, 2}.
cout << "." << endl;

return 0;
}
1. The Core Concept: Overlapping Sub problems

To reach the 4th stair, we must have come from either:

The 3rd stair (by taking 1 step).
The 2nd stair (by taking 2 steps).
Therefore, the total ways to reach stair n is the sum of the ways to reach (n-1) and (n-2). This is exactly
the Fibonacci Sequence logic!
2. Step-by-Step Logic Trace (n = 4)
When we call countWays(4), the computer builds a Recursion Tree. It explores the left branch entirely
before moving to the right.
The "Winding" Phase (Going Down)
Step 1: countWays(4) calls countWays(3) and countWays(2).
Step 2: countWays(3) (left side) calls countWays(2) and countWays(1).
Step 3: countWays(2) calls countWays(1) and countWays(0).
Step 4: Base Case Hit! countWays(1) returns 1. countWays(0) returns 1.
The "Unwinding" Phase (Building the Answer)
Resolve countWays(2): 1 (from 1) + 1 (from 0) =2.
Resolve countWays(3): It needs countWays(2) (which we just found is 2) + countWays(1) (which is 1).
Total =3.
Final Step for countWays(4): It takes the result of countWays(3) (which is 3) and adds it to the result of
the right branch countWays(2) (which is 2).
Result: 3 + 2 = 5.
There are 5 ways to climb 4 stairs.
PROGRAM 2: Count Books

A librarian has a collection of n books stacked in a special way. To find a particular book, you must first look at the book on
the top, then recursively search the rest of the stack. If you find the book, you need to count how many books you had to
look at before finding it.
Task: Write a recursive function that takes the number of books n and the position of the target book and counts how many
books were looked at.

Input Format:
Two integers: n (total books) and target (the position of the book you are looking for).

Output Format:
Print the number of books looked at.

Sample Input:
n = 5, target = 3

Sample Output:
3 (You look at 1, then 2, then 3)
Solution: counts for n value.

import [Link];
public class Main {
public static int countBooks(int n, int target) {
if (n == target)
return 1;
return 1 + countBooks(n - 1, target);
}

public static void main(String[] args) {

Scanner scanner = new Scanner([Link]);
int n = [Link]();
int target =[Link]();
[Link](countBooks(n, target));
[Link]();
}
}

The function counts how many books you pass while going backward from n to target.
Function Reminder ________________________________________
public static int countBooks(int n, int target) { Call Stack View
if (n == target) countBooks(5,3)
return 1; countBooks(4,3)
return 1 + countBooks(n - 1, target); countBooks(3,3) → 1
} ________________________________________
________________________________________ Final Output
Step-by-Step Dry Run 3
Call 1: ________________________________________
countBooks(5, 3)
= 1 + countBooks(4, 3) Intuition
Call 2: You are counting how many numbers from 5 down to 3
countBooks(4, 3) (inclusive):
= 1 + countBooks(3, 3) 5→4→3
Call 3 (Base Case): That’s 3 steps, so output = 3
countBooks(3, 3) ________________________________________
= 1 ✅ (since n == target) Quick Formula :
________________________________________ For this function:
Unwinding (Returning values) result = (n - target) + 1
Now we go back step by step: For our case:
countBooks(3,3) = 1 (5 - 3) + 1 = 3
countBooks(4,3) = 1 + 1 = 2
countBooks(5,3) = 1 + 2 = 3
Solution: counts for target value:

#include <iostream>
using namespace std;

int countBooks(int n, int target) {

// New Base Case: Stop when we find the target
if (n == target) return 0;

if (n == 0) return 0;
return 1 + countBooks(n - 1, target);
}

int main() {
int n = 5;
int target = 3;
cout << "Books looked at before finding the target: " << countBooks(n, target) << endl;
return 0;
} Output:
Books looked at before finding the target: 5