DSA-in-JavaScript/08_recursion.md at main · thakurrahul99/DSA-in-JavaScript

Arey bacho! Jaldi se class mein aa jao aur whiteboard par apna dhyan lagao.

Pichle chapters mein humne Arrays, Matrices, Strings, aur Hashing ke patterns ko completely disassemble kiya. Humne seekha ki kaise Map aur Set ka use karke hum lookups ko average O(1) par le aate hain.

Lekin beta, jab hum deep data structures jaise Trees aur Graphs ki taraf badhte hain, ya dynamic programming aur backtracking ke complex maze ko solve karte hain, toh humare normal loops fail ho jate hain. Wahan humein ek aisi core programming technique ki zaroorat hoti hai jo complex problems ko asani se chote-chote subproblems mein break kar sake.

Aur usi superpower ka naam hai—Recursion!

Bohot se bache recursion se darrte hain kyunki unka mental model clear nahi hota aur unhe hamesha Stack Overflow ka darr rehta hai. Aaj hum recursion ko bilkul zero level se uthaenge aur coding ki aisi in-depth visualization karenge ki tum complex recursive codes ka behavior call stack par khud trace kar paoge.

Fatafat apni pen aur copy nikal lo, aur shuru karte hain Chapter 8: Recursion!

1. THE RECURSION MYSTIQUE: WHAT & WHY?

Recursion Kya Hai?

Kitabi bhasha mein bolein toh "Jab ek function apne hi andar se khud ko dobara call karta hai, toh us process ko Recursion kehte hain".

Lekin dimaag mein iska mental model kaise banayein?
Socho tum ek bohot lambi queue (line) mein khade ho movie ticket lene ke liye. Tum sabse peeche khade ho aur tumhein jaanna hai ki tumhara line mein kaunsa number hai.

   Ticket Counter ◄── [Person 1] ◄── [Person 2] ◄── [Person 3] ◄── [You]

Tum poori line ko traverse karke ginte hue counter tak nahi ja sakte (Kyunki line toot jayegi!). Tum kya karoge?

Tum apne aage wale person (Person 3) se poochoge: "Bhaiya, tumhara ticket line mein kya number hai?"
Person 3 ko bhi apna number nahi pata, toh woh apne aage wale (Person 2) se poochega.
Person 2 apne aage wale (Person 1) se poochega.
Person 1 seedhe ticket counter wale se poochkar bolega: "Main toh 1st number par hoon!" (Yeh humara Base Case hai).
Person 1 ka answer milte hi, Person 2 bolega: "Accha, tum 1st ho, toh main 1 + 1 = 2nd number par hoon." (Yeh answer ka Combine/Unwinding step hai).
Person 3 bolega: "Main 2 + 1 = 3rd number par hoon."
Aur aakhir mein Person 3 se answer milte hi tum kahoge: "Main 3 + 1 = 4th number par hoon!"

Yahi real-life process Recursion hai! Tumne apni badi problem (poori line ka count) ko smaller subproblems (aage wale ka index) mein convert kar diya aur answers ko peeche se combine karte hue solve kar liya.

Another real-life analogy: Russian Nesting Dolls (Matryoshka dolls). Ek badi doll kholte ho, toh andar bilkul same structure ki thodi choti doll milti hai. Use kholte ho toh aur choti milti hai, jab tak tum aakhri sabse choti doll par na pahunch jao jise khola nahi ja sakta (Base case).

2. THE THREE SACRED PILLARS OF A RECURSIVE FUNCTION

Ek perfect recursive function hamesha teen cheezon par khada hota hai:

                  ┌──────────────────────────────────────────┐
                  │       RECURSIVE STRUCTURE PILOT          │
                  ├──────────────────────────────────────────┤
                  │                                          │
                  │   1. BASE CASE (The Stop Button 🛑)       │
                  │      if (n === 0) return constant;       │
                  │                                          │
                  │   2. RECURSIVE CASE (The Self Call 🔄)    │
                  │      return function(n - 1) * modifier;  │
                  │                                          │
                  │   3. WORK TOWARD BASE CASE (Shrinkage 📉)│
                  │      Input (n) must reduce towards 0!    │
                  │                                          │
                  └──────────────────────────────────────────┘

Base Case (The Stop Button 🛑):
Woh minimum input condition jahan recursion ko rukna hai aur bina kisi self-call ke direct value return karni hai. Agar base case nahi hoga ya galat hoga, toh function chalta hi chala jayega aur computer crash ho jayega.
Recursive Case:
Woh logic jahan function khud ko dobara call karta hai ek smaller subproblem ko solve karne ke liye.
Progress Toward Base Case:
Har recursive call ke waqt input size reduce hona chahiye taaki hum base case ki taraf badhein (jaise n ko n - 1 karna). Agar input size reduce nahi hoga, toh hum kabhi stop button tak nahi pahunch paenge.

3. UNDER THE HOOD: CALL STACK & THE ANATOMY OF STACK FRAMES

Bacho, recursion ko dhang se samajhne ke liye humein memory level par jaana hoga.

Jab bhi JavaScript mein koi function call hota hai, toh V8 engine use memory ke Call Stack par daal deta hai. V8 engine call stack par ek Stack Frame (Activation Record) create karta hai, jismein us function call ke local variables aur parameters store hote hain.

Call Stack strictly LIFO (Last In, First Out) principle follow karta hai—yaani jo function sabse aakhir mein call hua hai, woh stack se sabse pehle khatam (resolve) hoga.

Visualizing Stack Frames in Action:

Chalo ek simple recursion ko visualize karte hain: printN(3) jo 3 se 1 tak numbers print karta hai.

function printN(n) {
    if (n === 0) return; // Base Case
    console.log(n);
    printN(n - 1);       // Recursive Call with Shrunk Input
}
printN(3);

Call Stack ka Graphical Lifecycle:

   Step 1: printN(3)      Step 2: printN(2)      Step 3: printN(1)      Step 4: printN(0) (Base Case)
   ┌───────────────┐      ┌───────────────┐      ┌───────────────┐      ┌───────────────┐
   │               │      │               │      │               │      │  printN(0)    │  <-- Pops instantly!
   ├───────────────┤      ├───────────────┤      ┌───────────────┐      ├───────────────┤
   │               │      │               │      │  printN(1)    │      │  printN(1)    │
   ├───────────────┤      ┌───────────────┐      ├───────────────┤      ├───────────────┤
   │               │      │  printN(2)    │      │  printN(2)    │      │  printN(2)    │
   ┌───────────────┐      ├───────────────┤      ├───────────────┤      ├───────────────┤
   │  printN(3)    │      │  printN(3)    │      │  printN(3)    │      │  printN(3)    │
   └───────────────┘      └───────────────┘      └───────────────┘      └───────────────┘

What is Stack Overflow? (The Crash! 💥)

Memory limited hoti hai. Agar hum infinite recursive loop chala dein (bina base case ke ya galat parameters ke), toh call stack frames se bhar jata hai aur use aage spaces allocation nahi milti. JavaScript engine instantly execution halt karke ek error throw karta hai: RangeError: Maximum call stack size exceeded.

4. RECURSION VS ITERATION (THE ARCHITECTURAL SHOWDOWN)

Interviews mein poocha jata hai ki "Sir, loop chalayein ya recursion use karein?" Dono ke tradeoffs ko is table se dhyan se samjho:

Feature	Iteration (Loops)	Recursion
Memory Footprint	O(1) Space (constant memory). Purane variables hi update hote hain, koi stack frames nahi bante.	O(N) Auxiliary Space. Har recursive call ek naya stack frame memory par hold karti hai jab tak base case resolve na ho jaye.
Execution Speed	Fast. Engine levels par loops bohot optimized hote hain.	Relatively slow. Function calls ka overhead, activation frames allocation, aur stack insertions time lete hain.
Code Readability	Agar problem bohot deep aur complex ho (jaise tree traversal), toh iterative code bohot ganda aur bada ho jata hai.	Extremely elegant aur compact. 15 lines ka code 3-4 lines mein resolve ho jata hai.

5. DIRECT VS INDIRECT, HEAD VS TAIL RECURSION

Recursive patterns alag-alag types ke hote hain:

Direct Recursion:
Jab function A seedhe apne hi andar se function A ko call kare.
Indirect Recursion (Mutual Recursion):
Jab function A call kare function B ko, aur function B wapas se call kare function A ko. Ek loop/cycle ban jata hai.
Head Recursion:
Agar recursive call function ki shuruat mein hi ho jaye, aur bacha hua saara logic (work) us call ke baad execute ho. Isme "unwinding phase" (wapas aate waqt) saara kaam hota hai.
Tail Recursion:
Agar recursive call function ka absolutely last statement ho. recursive call ke baad koi work bacha hi nahi hota. Modern compilers (jaise V8's Tail Call Optimization - TCO) tail recursion ko internally loop mein convert kar dete hain, jisse space complexity O(1) par drop ho jati hai!

6. THE RECURSIVE MINDSET: HOW TO THINK RECURSIVELY?

Bacho, recursion seekhne ka sabse bada secret hai Trust (Trust your function)! Is checklist ko hamesha dimaag mein betha lo jab bhi recursive code likhna ho:

Identify the Smallest Problem (Base Case): Sabse chota aur asaan input kya ho sakta hai jiska answer mujhe pehle se pata hai? (e.g., factorial(0) === 1).
The Smaller Same Problem Conversion: Main apni current problem ko thode chote same subproblem mein kaise convert kar sakta hoon?.
Trust the Sub-call: Trust karo ki agar main function(n - 1) ko call karunga, toh woh bilkul sahi answer laakar dega. Mujhe uske andar deep loop trace mein nahi ghusna hai.
Combine the Answers: Sub-call se jo chota answer aaya, usme main kya work jodoon taaki meri current problem solve ho jaye?.

7. CORE PROBLEM SOLVING MASTERCLASS (STRUCTURED BREAKDOWNS)

Problem 1: Factorial of a Number

1. Understand:

Humein kisi non-negative integer n ka factorial nikalna hai (denote as n!).
5! = 5 * 4 * 3 * 2 * 1 = 120. 0! = 1.

2. Iterative Idea:

Ek simple loop lagao 1 se n tak aur elements ko multiply karte jao. Space: O(1).

3. Recursive Idea:

Smallest problem: factorial(0) or factorial(1) ka answer 1 hota hai.
Smaller same problem: 5! aur kuch nahi, balki 5 * 4! hai.
Mathematical relation: factorial(n) = n × factorial(n - 1).

4. Base Case Identify:

if (n === 0 || n === 1) return 1;

5. Recursive Case:

return n * factorial(n - 1);

6. Code:

function factorial(n) {
    if (n === 0 || n === 1) { // Base Case
        return 1;
    }
    return n * factorial(n - 1); // Recursive Case
}

7. Call Stack Dry Run (`factorial(4)`):

factorial(4) call hua → 4 * factorial(3) par hold ho gaya. Stack frame added.
factorial(3) call hua → 3 * factorial(2) par hold. Stack frame added.
factorial(2) call hua → 2 * factorial(1) par hold. Stack frame added.
factorial(1) call hua → 1 matches base case, returns 1 instantly. Stack frame pops.

8. Return/Unwinding Process:

factorial(1) returns 1 to factorial(2). factorial(2) computes 2 * 1 = 2 and returns it. Stack frame pops.
factorial(3) receives 2, computes 3 * 2 = 6 and returns it. Stack frame pops.
factorial(4) receives 6, computes 4 * 6 = 24 and returns it. Stack frame pops. Call Stack is empty!

9. Complexity:

Time Complexity: O(n). Function exactly n baar execute hota hai.
Space Complexity: O(n) Auxiliary Space recursion call stack frames hold karne ke liye.

Problem 2: Fibonacci Number (The Naive Recursion Dissection)

1. Understand:

Fibonacci sequence zero aur one se shuru hoti hai, aur har agla term pichle do terms ka addition hota hai.
Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21...
Humein N^{th} Fibonacci index value return karni hai.

2. Recursive Relation:

Smallest problem: fib(0) === 0, fib(1) === 1.
Smaller same problem: N^{th} Fibonacci term nikalne ke liye pichle do terms, i.e., (N-1)th aur (N-2)th terms ka addition karna hoga.
Formula: fib(n) = fib(n - 1) + fib(n - 2).

3. Code:

function fib(n) {
    if (n < 2) { // Base Case: Handles both 0 and 1
        return n;
    }
    return fib(n - 1) + fib(n - 2); // Double Branching Recursion
}

4. The Recursion Tree (`fib(4)`):

Bacho, dhyan se dekho is tree ko, isme double recursion ka saara sach chupa hai!

                         fib(4)
                        /      \
                    fib(3)      fib(2)
                   /     \     /     \
                fib(2)  fib(1)fib(1) fib(0)
               /     \
            fib(1)  fib(0)

5. Repeated Work & Performance Bottleneck 🚨:

Dhyan se dekho! fib(2) ko humne left branch mein bhi calculate kiya aur right branch mein bhi calculation dobara run ki.
Jaise-jaise n badhega, yeh redundant calculations exponentially badh jayengi!

Total Recursive Calls: Tree ka har element lagbhag 2 sub-branches split hota hai. Isiliye operations ka count 2^n ke scale par badhta hai.
DP Memoization Bridge: Future chapters mein hum dynamic programming (memoization) seekhenge, jahan hum ek baar computed values (jaise fib(2)) ko map/object mein store kar lenge taaki dobara calculation na karni pade. Isse complexity exponential se seedhe O(n) linear par drop ho jayegi.

6. Complexity:

Time Complexity: O(2^n) (Exponential height traversal).
Space Complexity: O(n) Auxiliary Space kyunki call stack par simultaneously maximum depth at any point sirf N frames tak hi touch karegi.

Problem 3: Sum of Array Elements recursively

1. Understand:

Humein ek array diya hai aur recursion use karke uske saare elements ka sum nikalna hai.
arr =, Sum = 15.

2. SDE Optimization (Popping vs. Slicing vs. Pointer Bounds) 💡:

Bachon, recursion se array sum nikalne ke teen raste hain. Tradeoffs samajhna zaroori hai:

Rasta A: Slicing (arr.slice): Hum har step par last element nikalenge aur bache array ko slice karke recursion mein bhejenge.
- Problem: slice() method internally array elements ko copy karta hai, jo har step par O(n) time aur space consume karta hai. Isse overall complexity degrade ho jayegi.
Rasta B: Pop Method (arr.pop): Array ke aakhir se element ko pop karke constant time O(1) mein operations chala sakte hain.
- Problem: Pop karne se original input array mutate (modify) ho jata hai, jo production code mein bad habit maani jati hai.
Rasta C: Pointer Bounds (Optimal SDE Way): Original array ko intact rakho aur bas ek variable pointer n (array length) pass karo, jo track karega ki humein kis index tak ka sum chahiye.

3. Code (Optimal Pointer Bounds Method):

function sumOfArray(arr, n) {
    // Base Case: Agar length 0 hai, sum matches 0
    if (n <= 0) {
        return 0;
    }
    // Work + Smaller Problem Recursive Call
    return arr[n - 1] + sumOfArray(arr, n - 1);
}

4. Dry Run (`arr =`, `n = 3`):

sumOfArray(arr, 3) → returns arr + sumOfArray(arr, 2) (i.e., 30 + sumOfArray(arr, 2))
sumOfArray(arr, 2) → returns 20 + sumOfArray(arr, 1)
sumOfArray(arr, 1) → returns 10 + sumOfArray(arr, 0)
sumOfArray(arr, 0) → base case hit, returns 0.
Unwinding: 10 + 0 = 10 → 20 + 10 = 30 → 30 + 30 = 60. Returns 60 (Correct!).

5. Complexity:

Time Complexity: O(n). (Looping equivalents).
Space Complexity: O(n) Auxiliary stack space.

Problem 4: Power of a Number (Iterative vs. Fast Powering)

1. Understand:

Humein x ko power n tak raise karna hai (i.e., x^n).

2. Brute Force Recursive (Linear):

Multiply x with power(x, n - 1). Time takes O(n).

3. Fast Powering Algorithm (Divide & Conquer):

"Sir, pichle chapters ke math lessons se humein pata hai ki dynamic subdivisions use ki ja sakti hain!"

Agar power even hai: 2^8 = (2^4)^2 = (2 × 2 × 2 × 2)^2. Yaani hum power ko directly aadha (half) kar sakte hain!
Agar power odd hai: 2^9 = 2 × 2^8.

4. JavaScript Code:

function fastPower(x, n) {
    if (n === 0) return 1; // Base case: Any number to power 0 is 1
    if (n < 0) { // Handles negative powers cleanly
        x = 1 / x;
        n = -n;
    }
    
    let halfPower = fastPower(x, Math.floor(n / 2)); // Divide Step
    
    if (n % 2 === 0) {
        return halfPower * halfPower; // Conquer even power
    } else {
        return x * halfPower * halfPower; // Conquer odd power
    }
}

5. Complexity:

Time Complexity: O(log n) (Directly problem space is halved at each recursion step!).
Space Complexity: O(log n) Stack Space recursion depth ke liye.

Problem 5: Check Palindrome recursively

1. Understand:

Humein check karna hai ki kya string recursive logic se palindrome hai ya nahi (jaise "racecar").

2. Recursive Strategy:

Agar string ki length 0 ya 1 hai, toh woh hamesha palindrome hogi (Base case).
Pehle aur aakhri character (start and end) ko compare karo. Agar mismatch ho, return false.
Agar matching ho, toh bachi hui inner substring (start + 1 to end - 1) ko recursively check karo.

function isPalindromeHelper(str, start, end) {
    if (start >= end) return true; // Base Case
    if (str[start] !== str[end]) return false; // Match Broken!
    
    return isPalindromeHelper(str, start + 1, end - 1); // Shrunk subproblem call
}

function isPalindrome(str) {
    return isPalindromeHelper(str, 0, str.length - 1);
}

Complexity: Time: O(n), Space: O(n) call stack space.

8. PARADIGM GATEWAY: DIVIDE & CONQUER & BACKTRACKING

Recursion humare advanced algorithmic paradigms ka entry gate hai:

                            RECURSION PARADIGMS
                                     │
           ┌─────────────────────────┴─────────────────────────┐
     Divide & Conquer                                     Backtracking
           │                                                   │
           ▼                                                   ▼
     - Split problem in half                       - DFS State-space search
     - Solve subparts independently                      - Build candidate answers
     - Merge back results                          - Undo (Backtrack) if invalid
     - E.g., Merge Sort                        - E.g., N-Queens

Divide and Conquer Connection:
Badi problem ko non-overlapping subproblems mein todna (Divide), un subproblems ko recursively solve karna (Conquer), aur unke answers ko fir se combine karna (Merge).
Examples: Binary Search, Merge Sort, Quick Sort.
Backtracking Connection:
Backtracking basically brute force search space exploration hai using recursive DFS. Hum candidate solutions build karte hain, aur agar kisi level par lagta hai ki yeh path galat hai, toh hum piche mudte hain (backtrack) aur dusre branches par explore karte hain. Stack/Recursion is process ko naturally rollback state memory provide karta hai.

9. COMMON MISTAKES (THE RECURSION RED FLAGS! ⚠️)

SDE coding rounds mein in bugs ko door rakhna:

Missing Base Case:
Function recursively chalta jayega jab tak call stack overflow na ho jaye. Always write base case first!
Base Case Unreachable (Infinite Loop):
Kaha if (n === 0) return, par parameter update kiya n + 1 instead of n - 1. Parameters are expanding away from base case boundaries.
Wrong/Missing Return Statements:
Forgetting to write return keyword in the recursive call statement. factorial(n - 1) call toh ho jayega par main function runtime par undefined return dega!
Mutating Inputs Slicing Arrays:
Using array slicing (arr.slice) inside loops or recursion to shrink array bounds, degrading time performance to quadratic limits. Always use index boundaries (start/end pointers).

10. CLASSROOM PRACTICE ROOM (EASY → MEDIUM → HARD)

🚀 ** Whiteboard bilkul clean hai dosto! Chalo, pehle khud base cases aur relations dhoondho aur fir explanations padhna!**

Problem 1 (Easy): Reverse a String recursively

Problem Statement: Ek string str di gayi hai, use recursively reverse karke return karo.
Identify:
- Base Case kya hona chahiye? Jab string empty ho ya single letter ho, toh reverse is itself.
- Recursive relation? Last character ko nikalo aur use pehle character se swap or concatenate karo smaller recursive parts par.

// SDE Solution
function reverseString(str) {
    if (str.length <= 1) return str; // Base Case
    
    // Last char + recursive call of bacha hua parts
    return str[str.length - 1] + reverseString(str.slice(0, str.length - 1));
}

Complexity: Time: O(n^2) (due to slice copy), Space: O(n) stack space. (Optimization can be achieved using char array pointer swaps).

Problem 2 (Medium): Print N to 1 without Loops

Problem Statement: Ek positive integer N diya hai, humein bina kisi for ya while loop ke sequentially N se 1 tak ke numbers print karne hain.
Identify:
- Base Case? N === 0 hone par return ho jao.
- Work Step? Print N and call recursively for N - 1.

// SDE Solution
function printNToOne(N) {
    if (N === 0) return; // Base Case
    
    console.log(N);       // Work
    printNToOne(N - 1);  // Progress
}

Complexity: Time: O(n), Space: O(n) Auxiliary Stack space.

Problem 3 (Hard): Generate All Subsets of a Set (Power Set)

Problem Statement: Humein ek set of unique integers nums diya gaya hai. Humein iske saare possible subsets (Power Set) recursively generate karke return karne hain.
Identify:
- Base Case? Agar current index i array ke size ke barabar ho jaye, toh humne ek complete candidate array choose kar liya hai, use result list mein add karke return ho jao.
- Choice Pattern (The SDE Choice Magic 💡): Har element par humare paas do choices hoti hain:
  1. Include choice: Element ko subset card list mein lo aur aage badho.
  2. Exclude choice: Element ko subset card list mein mat lo aur aage badho.

// SDE Masterclass Solution (Backtracking/Recursion Combination)
function generateSubsets(nums) {
    const result = [];
    
    function backtrack(index, currentSubset) {
        // Base Case: reached end of choices array bounds
        if (index === nums.length) {
            result.push([...currentSubset]); // Deep copy of candidate
            return;
        }
        
        // Choice 1: Include the current element
        currentSubset.push(nums[index]);
        backtrack(index + 1, currentSubset);
        
        // Choice 2: Exclude the current element (Backtrack Step)
        currentSubset.pop();
        backtrack(index + 1, currentSubset);
    }
    
    backtrack(0, []);
    return result;
}

Complexity: Time Complexity: O(2^n) (since total subsets generated of size N is exactly 2^N). Space Complexity: O(n) auxiliary stack depth space.

CHAPTER END SUMMARY

Completed Concepts:

Foundational definition of Recursion, stop conditions, and progress.
Memory structures: Stack Frames, LIFO Stack layouts, and Stack Overflow reasons.
Tradeoffs: Recursion readability vs Iteration memory efficiency.
Types: Head vs Tail optimization configurations.
Mathematical problem solving: Factorial, Fibonacci trees, Fast exponentiation logarithmic runs.
Recursive traversals: Sum of Array and Palindromes.

Recursive Thinking Checklist (Dimaag mein lock karo!):

Kya base case strictly handles base values of n <= 1?.
Kya dynamic input shrink target condition base bounds ki taraf badh rahi hai?.
Kya double recursive branches repeated operations avoid karne ke liye DP links use kar rahi hain?.

FilesExpand file tree

08_recursion.md

Latest commit

History

08_recursion.md

File metadata and controls

1. THE RECURSION MYSTIQUE: WHAT & WHY?

Recursion Kya Hai?

2. THE THREE SACRED PILLARS OF A RECURSIVE FUNCTION

3. UNDER THE HOOD: CALL STACK & THE ANATOMY OF STACK FRAMES

Visualizing Stack Frames in Action:

Call Stack ka Graphical Lifecycle:

What is Stack Overflow? (The Crash! 💥)

4. RECURSION VS ITERATION (THE ARCHITECTURAL SHOWDOWN)

5. DIRECT VS INDIRECT, HEAD VS TAIL RECURSION

6. THE RECURSIVE MINDSET: HOW TO THINK RECURSIVELY?

7. CORE PROBLEM SOLVING MASTERCLASS (STRUCTURED BREAKDOWNS)

Problem 1: Factorial of a Number

1. Understand:

2. Iterative Idea:

3. Recursive Idea:

4. Base Case Identify:

5. Recursive Case:

6. Code:

7. Call Stack Dry Run (factorial(4)):

8. Return/Unwinding Process:

9. Complexity:

Problem 2: Fibonacci Number (The Naive Recursion Dissection)

1. Understand:

2. Recursive Relation:

3. Code:

4. The Recursion Tree (fib(4)):

5. Repeated Work & Performance Bottleneck 🚨:

6. Complexity:

Problem 3: Sum of Array Elements recursively

1. Understand:

2. SDE Optimization (Popping vs. Slicing vs. Pointer Bounds) 💡:

3. Code (Optimal Pointer Bounds Method):

4. Dry Run (arr =, n = 3):

5. Complexity:

Problem 4: Power of a Number (Iterative vs. Fast Powering)

1. Understand:

2. Brute Force Recursive (Linear):

3. Fast Powering Algorithm (Divide & Conquer):

4. JavaScript Code:

5. Complexity:

Problem 5: Check Palindrome recursively

1. Understand:

2. Recursive Strategy:

8. PARADIGM GATEWAY: DIVIDE & CONQUER & BACKTRACKING

9. COMMON MISTAKES (THE RECURSION RED FLAGS! ⚠️)

10. CLASSROOM PRACTICE ROOM (EASY → MEDIUM → HARD)

Problem 1 (Easy): Reverse a String recursively

Problem 2 (Medium): Print N to 1 without Loops

Problem 3 (Hard): Generate All Subsets of a Set (Power Set)

CHAPTER END SUMMARY

Completed Concepts:

Recursive Thinking Checklist (Dimaag mein lock karo!):

7. Call Stack Dry Run (`factorial(4)`):

4. The Recursion Tree (`fib(4)`):

4. Dry Run (`arr =`, `n = 3`):