Recursion vs Iteration When Each Wins in DSA Typescript - Visual Comparison

Concept Flow - Recursion vs Iteration When Each Wins

Start Problem

↓

Choose Approach

↓

Use Recursion

↓

Recursive Calls

↓

Base Case?

↓

Return Result

↓

Solution

Shows the decision flow between using recursion or iteration to solve a problem, ending with the solution.

Execution Sample

DSA Typescript

function factorialRec(n: number): number {
  if (n <= 1) return 1;
  return n * factorialRec(n - 1);
}

function factorialIter(n: number): number {
  let result = 1;
  for (let i = 2; i <= n; i++) result *= i;
  return result;
}

Calculates factorial of n using recursion and iteration.

Execution Table

Step	Operation	Call Stack / Loop Index	Intermediate Result	Visual State
1	Call factorialRec(4)	Stack: [4]	N/A	Stack: factorialRec(4)
2	Call factorialRec(3)	Stack: [4,3]	N/A	Stack: factorialRec(4) -> factorialRec(3)
3	Call factorialRec(2)	Stack: [4,3,2]	N/A	Stack: factorialRec(4) -> factorialRec(3) -> factorialRec(2)
4	Call factorialRec(1)	Stack: [4,3,2,1]	Return 1	Stack bottom reached, base case
5	Return from factorialRec(1)	Stack: [4,3,2]	1	Return 1 to factorialRec(2)
6	Calculate 2 * 1	Stack: [4,3,2]	2	Return 2 to factorialRec(3)
7	Return from factorialRec(2)	Stack: [4,3]	2	Return 2 to factorialRec(3)
8	Calculate 3 * 2	Stack: [4,3]	6	Return 6 to factorialRec(4)
9	Return from factorialRec(3)	Stack: [4]	6	Return 6 to factorialRec(4)
10	Calculate 4 * 6	Stack: [4]	24	Return 24 to main
11	Return from factorialRec(4)	Stack: []	24	Stack empty, recursion ends
12	Start factorialIter(4)	i=2	result=1	Loop start
13	Multiply result by i=2	i=2	result=2	result updated to 2
14	Increment i to 3	i=3	result=2	Loop continues
15	Multiply result by i=3	i=3	result=6	result updated to 6
16	Increment i to 4	i=4	result=6	Loop continues
17	Multiply result by i=4	i=4	result=24	result updated to 24
18	Increment i to 5	i=5	result=24	Loop ends (i > n)
19	Return result	N/A	24	Iteration ends, result returned

💡 Recursion ends when base case n <= 1 is reached; iteration ends when loop index exceeds n.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 10	After Step 11	After Step 12	After Step 17	Final
n (recursion)	4	1 (base case)	2	4	N/A	N/A	N/A	N/A
Call Stack Depth	1	4	3	1	0	N/A	N/A	N/A
i (iteration)	N/A	N/A	N/A	N/A	N/A	2	4	5
result (iteration)	1	N/A	N/A	N/A	N/A	1	24	24

Key Moments - 3 Insights

Why does recursion use a call stack and iteration uses a loop variable?

Recursion creates new function calls stacked on top of each other (see steps 1-11 in execution_table), while iteration uses a single loop variable to repeat actions (see steps 12-19). This difference affects memory use and flow control.

When does recursion stop calling itself?

Recursion stops when it reaches the base case (n <= 1), as shown at step 4 where factorialRec(1) returns 1, ending further calls.

Why might iteration be preferred over recursion?

Iteration uses less memory because it doesn't add to the call stack. This is clear in steps 12-19 where a simple loop updates variables without stacking calls.

Visual Quiz - 3 Questions

Look at the execution_table, what is the call stack depth at step 6?

A 3

B 4

C 2

D 1

💡 Hint

Check the 'Call Stack / Loop Index' column at step 6 in execution_table.

At which step does the iteration loop end?

A Step 17

B Step 19

C Step 18

D Step 12

💡 Hint

Look for the step where the loop index exceeds n in execution_table.

If the base case in recursion was changed to n <= 0, what would happen?

A Recursion would stop earlier

B Recursion would never stop for n=1

C No change in recursion behavior

D Iteration would be affected

💡 Hint

Refer to the base case condition in execution_table steps 3-4.

Concept Snapshot

Recursion calls the same function with smaller inputs until a base case stops it.
Iteration uses loops to repeat actions until a condition fails.
Recursion uses more memory due to call stack; iteration is memory efficient.
Use recursion for problems naturally defined by smaller subproblems.
Use iteration for simple repeated tasks or when memory is limited.

Full Transcript

This visualization compares recursion and iteration using factorial calculation. Recursion breaks the problem into smaller calls until a base case is reached, stacking calls in memory. Iteration uses a loop to multiply numbers step by step. The execution table shows recursion call stack growth and return values, and iteration loop progress with variable updates. Key moments clarify why recursion uses a call stack and when it stops, and why iteration can be more memory efficient. The quiz tests understanding of call stack depth, loop termination, and base case importance.

Practice

1. Which scenario is best suited for using recursion instead of iteration?

easy

A. When the problem requires simple repeated loops

B. When you want to avoid function call overhead

C. When the problem can be divided into similar smaller problems

D. When memory usage must be minimal

Solution

1. Step 1: Understand recursion vs iteration use cases

   Recursion works well when a problem can be broken down into smaller, similar subproblems, like tree traversals or factorial calculation. Iteration is better for simple repeated tasks without nested subproblems, and it avoids function call overhead.

2. Final Answer:

   When the problem can be divided into similar smaller problems -> Option C

3. Quick Check:

   Recursion = divide and conquer [OK]

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

Common Mistakes:

• Thinking iteration is always faster
• Ignoring function call overhead in recursion
• Confusing recursion with simple loops

2. Which of the following is the correct syntax to write a recursive function in TypeScript?

easy

A. function recurse(n: number): number { if (n <= 1) return 1; return n * recurse(n - 1); }

B. function recurse(n: number): number { while (n > 1) { n--; } return n; }

C. function recurse(n: number): number { for (let i = 0; i < n; i++) { return i; } }

D. function recurse(n: number): number { if (n == 0) return 0; else return n + 1; }

Solution

1. Step 1: Identify recursive call and base case

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

2. Final Answer:

   function recurse(n: number): number { if (n <= 1) return 1; return n * recurse(n - 1); } -> Option A

3. Quick Check:

   Recursive function must call itself with smaller input [OK]

Hint: Look for function calling itself with smaller input [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Using loops instead of recursive calls
• Returning inside a loop without recursion

3. What will be the output of the following TypeScript code?

function factorial(n: number): number {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(4));

medium

A. 10

B. 24

C. 16

D. Error

Solution

1. Step 1: Trace recursive calls for factorial(4)

   factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1)=1. Then: factorial(2)=2*1=2, factorial(3)=3*2=6, factorial(4)=4*6=24. Output: 24.

2. Final Answer:

   24 -> Option B

3. Quick Check:

   4! = 24 [OK]

Hint: Factorial n! = n * (n-1)! [OK]

Common Mistakes:

• Confusing factorial with sum
• Forgetting base case returns 1
• Miscounting recursive calls

4. Identify the error in this recursive function and choose the fix:

function sumToN(n: number): number {
  return n + sumToN(n - 1);
}

medium

A. Add a base case to stop recursion when n <= 0

B. Change return to console.log to print values

C. Replace recursion with a for loop

D. Remove the parameter n

Solution

1. Step 1: Identify and fix the missing base case

   The function calls itself without a stopping condition, causing infinite recursion and stack overflow. Add if (n <= 0) return 0; to stop recursion when n <= 0.

2. Final Answer:

   Add a base case to stop recursion when n <= 0 -> Option A

3. Quick Check:

   Base case prevents infinite recursion [OK]

Hint: Always add base case to recursive functions [OK]

Common Mistakes:

• Forgetting base case causes infinite recursion
• Trying to fix by removing parameters
• Confusing printing with returning

5. You need to process a large dataset with a depth of 10,000 levels. Which approach is better and why?

Options:
A) Use recursion because it is easier to write.
B) Use recursion with no base case.
C) Use iteration to avoid stack overflow errors.
D) Use iteration but with no loop control.

hard

A. Use recursion because it is easier to write.

B. Use recursion with no base case.

C. Use iteration but with no loop control.

D. Use iteration to avoid stack overflow errors.

Solution

1. Step 1: Analyze stack limits for deep recursion

   Recursion uses the call stack, which has limited size. Depth of 10,000 risks stack overflow. Iteration uses loops without adding to call stack, safely handling large depths.

2. Final Answer:

   Use iteration to avoid stack overflow errors. -> Option D

3. Quick Check:

   Deep tasks need iteration to prevent stack overflow [OK]

Hint: Deep recursion risks stack overflow; prefer iteration [OK]

Common Mistakes:

• Assuming recursion always better for readability
• Ignoring stack size limits
• Using recursion without base case