Javascript Module 25

  Module 25 : Javascript Recursion  

🔍 1. Introduction to Recursion

🔁 What is Recursion?

Recursion is a programming technique where a function calls itself to solve a smaller instance of the same problem.

🔄 “A recursive function solves a problem by solving smaller subproblems of the same type.”

📑 2. Anatomy of a Recursive Function

A recursive function typically consists of two parts:

Base Case:

Stops the recursion to prevent infinite loops.

Recursive Case:

The function calls itself with a modified argument moving towards the base case.

✅ Example 1: Factorial of a Number

javascript

code

function factorial(n) { // Base Case if (n === 0) return 1; // Recursive Case return n * factorial(n - 1); } console.log(factorial(5)); // Output: 120

📖 Explanation:

factorial(5) calls factorial(4), which calls factorial(3)... and so on.

Eventually factorial(0) returns 1, and the results are multiplied back up.

🔍 3. How Recursion Works (Under the Hood)

Every recursive call adds a new frame to the call stack.

Example:

ruby

code

factorial(3)

=> 3 * factorial(2)

       => 2 * factorial(1)

              => 1 * factorial(0)

                     => 1

Stack:

factorial(3)

factorial(2)

factorial(1)

factorial(0) → returns 1

 4.  Visualize Recursion with Console

Log every recursive call to understand the flow.

javascript code

function factorial(n) { console.log("Calling factorial with n = " + n); if (n === 0) return 1; const result = n * factorial(n - 1); console.log("Returning " + result + " for n = " + n); return result; } factorial(4);

💡 What You'll Observe:

How the function goes "deeper"

When it starts "returning"

Order of function calls

🧮 5.  Example: Sum of Array Elements

javascript code

function sumArray(arr, index = 0) { if (index === arr.length) return 0; return arr[index] + sumArray(arr, index + 1); } console.log(sumArray([1, 2, 3, 4])); // Output: 10

✅ Practical Use:

Used in algorithms like:

Tree traversals

Backtracking

Searching and Sorting (Merge Sort, Quick Sort)

📂 6. Types of Recursion

Type

Description

Example

Tail Recursion

Recursive call is the last statement.

Used in optimizations

Head Recursion

Recursive call is before any computation.

Tree Recursion

Calls itself more than once per invocation.

Fibonacci

Indirect Recursion

Function A calls B, and B calls A

Rare

📘 7. Example 2: Fibonacci Sequence

javascript code

function fibonacci(n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); } console.log(fibonacci(5)); // Output: 5

⚠️ Performance Warning: Exponential time complexity due to repeated calculations. Use memoization for optimization.

🧠 8. Compare Recursive vs Iterative

Write both recursive and iterative solutions to find factorial.

javascript code

// Iterative function factorialIterative(n) { let result = 1; for(let i = 2; i <= n; i++) { result *= i; } return result; } // Recursive function factorialRecursive(n) { if (n === 0) return 1; return n * factorialRecursive(n - 1); }

🔍  Analysis:

Compare performance for large n

Observe call stack overflow

Time the execution

📚 9. Exercises with Explanation

📝 Exercise 1:

Write a recursive function to reverse a string.

javascript code

function reverseString(str) { if (str === "") return ""; return reverseString(str.substr(1)) + str.charAt(0); }

Explanation:

reverseString("abc") → reverseString("bc") + "a" → reverseString("c") + "b" + "a"

📝 Exercise 2:

Write a recursive function to count the number of digits in a number.

javascript

 code

function countDigits(n) { if (n < 10) return 1; return 1 + countDigits(Math.floor(n / 10)); }

 10. Recursive File Search (Node.js)

Use recursion to walk through directories and list files.

javascript

 code

const fs = require('fs'); const path = require('path'); function walk(dir) { const files = fs.readdirSync(dir); files.forEach(file => { const filepath = path.join(dir, file); const stat = fs.statSync(filepath); if (stat.isDirectory()) { walk(filepath); } else { console.log("File:", filepath); } }); } walk('./'); // run on root folder

🔬 11. Research-Based Understanding

📖 Topics to Explore Further:

Tail Call Optimization (TCO)

Some JS engines like V8 can optimize tail calls.

Stack Overflow in Recursion

Deep recursion without optimization can crash.

Recursion vs Iteration

Recursion is elegant; iteration is generally more memory efficient.

Memoization in Recursive Functions

Great for optimizing exponential recursive calls (e.g., Fibonacci)

💡 12. When to Use Recursion

✅ Use recursion when:

Problem has a recursive structure (e.g., Trees, Graphs)

Depth is manageable

Clarity is more important than performance

❌ Avoid recursion when:

Stack depth is too large

Performance is critical

✅ 13. Summary

Concept

Key Point

Recursive Function

A function that calls itself

Base Case

Stops the recursion

Call Stack

Stores recursive calls

Tail Recursion

Optimizable in some JS engines

Practical Uses

Trees, Algorithms, Filesystem traversal

Practice

Factorials, Arrays, Strings, File Systems

📘 Final Challenge

🎯 Write a recursive function to flatten nested arrays

javascript code

function flattenArray(arr) { return arr.reduce((acc, val) => Array.isArray(val) ? acc.concat(flattenArray(val)) : acc.concat(val) , []); } console.log(flattenArray([1, [2, [3, 4]], 5])); // Output: [1, 2, 3, 4, 5]