Why Recursion Exists and What Loops Cannot Express Cleanly in DSA Javascript - Quick Recap

Recall & Review

beginner

What is recursion in simple terms?

Recursion is when a function calls itself to solve smaller parts of a problem until it reaches a simple case it can solve directly.

beginner

Why do we need recursion when we have loops?

Loops repeat actions but can't easily handle problems that break down into smaller similar problems, like tree traversals or exploring choices. Recursion handles these naturally.

intermediate

Give an example of a problem that loops cannot express cleanly but recursion can.

Navigating a family tree or folder structure is hard with loops because the depth is unknown. Recursion can explore each branch easily by calling itself for each child.

beginner

What is a base case in recursion and why is it important?

A base case is the simplest problem that recursion can solve directly without calling itself again. It stops the recursion from going forever.

intermediate

How does recursion help in expressing problems with unknown or variable depth?

Recursion naturally handles unknown depth by calling itself for each smaller part until it reaches the base case, unlike loops which need fixed repetition counts.

Which of these problems is best solved using recursion?

A Calculating the sum of numbers from 1 to 100

B Printing numbers from 1 to 10

C Traversing a folder structure with unknown depth

D Repeating a task 5 times

Traversing a folder structure with unknown depth is best handled by recursion because the depth and number of folders are not fixed.

What stops a recursive function from running forever?

A A base case that ends recursion

B Calling the function twice

C A loop inside the function

D Using a counter variable

A base case is a simple condition that stops the recursive calls, preventing infinite loops.

Why can't loops easily replace recursion for some problems?

A Loops are slower

B Loops can't handle problems with unknown or variable depth cleanly

C Loops use more memory

D Loops are harder to write

Loops require a fixed number of repetitions, so they struggle with problems where the depth or size is unknown or changes.

Which of these is NOT a characteristic of recursion?

A Function calls itself

B Has a base case

C Breaks problem into smaller parts

D Always uses loops inside

Recursion does not always use loops inside; it relies on self-calling and base cases.

What is a common real-life example to explain recursion?

A Looking at a mirror reflecting another mirror

B Filling a bucket with water

C Walking in a straight line

D Counting steps on a staircase

Looking at mirrors reflecting each other shows a repeated pattern calling itself, similar to recursion.

Explain why recursion is useful for problems with unknown depth or branching, and why loops struggle with these.

Think about exploring folders or family trees.

Describe the role of the base case in recursion and what happens if it is missing.

What stops the function from calling itself forever?

Practice

1. Why do we use recursion instead of loops in some problems?
function factorial(n) { if (n === 0) return 1; return n * factorial(n - 1); }

easy

A. Loops are always slower than recursion.

B. Recursion can express problems with self-similar structure more naturally.

C. Recursion uses less memory than loops.

D. Loops cannot perform repeated actions.

Solution

1. Step 1: Understand recursion's purpose

   Recursion solves problems by breaking them into smaller similar problems, like factorial breaking n! into n * (n-1)!.

2. Step 2: Compare recursion and loops

   Loops repeat actions but do not naturally express self-similar or nested structures, which recursion handles clearly.

3. Final Answer:

   Recursion can express problems with self-similar structure more naturally. -> Option B

4. Quick Check:

   Recursion = natural for self-similar problems [OK]

Hint: Recursion fits problems breaking into smaller similar parts [OK]

Common Mistakes:

• Thinking loops are always slower
• Believing recursion uses less memory
• Assuming loops cannot repeat

2. Which of the following is the correct syntax to define a recursive function in JavaScript?

easy

A. function recurse(n) { for(let i=0; i

B. function recurse(n) { while(n > 0) recurse(n - 1); }

C. function recurse(n) { if (n > 0) return n; }

D. function recurse(n) { if (n <= 0) return; recurse(n - 1); }

Solution

1. Step 1: Identify recursive call structure

   function recurse(n) { if (n <= 0) return; recurse(n - 1); } calls itself with a smaller argument and has a base case to stop recursion.

2. Step 2: Check other options for recursion correctness

   The options using for or while loops include recursive calls but lack base cases, leading to infinite recursion. The option that returns n without a recursive call is not recursive.

3. Final Answer:

   function recurse(n) { if (n <= 0) return; recurse(n - 1); } -> Option D

4. Quick Check:

   Correct recursion has base case and self-call [OK]

Hint: Look for base case and self-call in function [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Using loops instead of recursion
• No recursive call inside function

3. What is the output of this recursive function?

function sumTo(n) { if (n === 0) return 0; return n + sumTo(n - 1); } console.log(sumTo(3));

medium

A. 6

B. 3

C. 0

D. Error

Solution

1. Step 1: Trace recursive calls

   sumTo(3) calls sumTo(2), sumTo(1), sumTo(0). sumTo(0) returns 0.

2. Step 2: Calculate return values

   sumTo(1) = 1 + 0 = 1, sumTo(2) = 2 + 1 = 3, sumTo(3) = 3 + 3 = 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Sum 1+2+3 = 6 [OK]

Hint: Add numbers down to zero recursively [OK]

Common Mistakes:

• Confusing base case return value
• Adding incorrectly during return
• Expecting loop output instead

4. Find the error in this recursive function that tries to calculate factorial:

function factorial(n) { if (n === 0) return 1; else return n * factorial(n); }

medium

A. Recursive call uses same argument causing infinite recursion

B. Return statement is missing

C. Should use a loop instead of recursion

D. Missing base case for n < 0

Solution

1. Step 1: Check recursive call argument

   The function calls factorial(n) again without reducing n, causing infinite recursion.

2. Step 2: Identify fix

   The recursive call should be factorial(n - 1) to move toward base case.

3. Final Answer:

   Recursive call uses same argument causing infinite recursion -> Option A

4. Quick Check:

   Recursive call must reduce argument [OK]

Hint: Ensure recursive call moves toward base case [OK]

Common Mistakes:

• Not reducing argument in recursive call
• Ignoring base case
• Confusing recursion with loops

5. Which problem below is best solved using recursion rather than loops because it involves nested self-similar structure?

hard

A. Calculating the sum of numbers from 1 to n

B. Finding the maximum value in a flat array

C. Traversing a directory tree to list all files and folders

D. Repeating a task 10 times

Solution

1. Step 1: Analyze problem structures

   Sum and max in flat arrays are simple linear tasks suited for loops.

2. Step 2: Identify nested self-similar structure

   Directory trees have folders inside folders, a nested structure best handled by recursion.

3. Final Answer:

   Traversing a directory tree to list all files and folders -> Option C

4. Quick Check:

   Nested structures = recursion best [OK]

Hint: Use recursion for nested or tree-like data [OK]

Common Mistakes:

• Using recursion for simple linear tasks
• Ignoring nested structure complexity
• Confusing repetition with recursion need