Why Recursion Exists and What Loops Cannot Express Cleanly in DSA C++ - 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 already have loops?

Recursion helps solve problems that have a natural 'divide and conquer' structure or nested patterns that loops find hard to express clearly.

intermediate

Give an example of a problem where loops are not clean but recursion is natural.

Calculating factorial or traversing a tree structure is easier and cleaner with recursion than with loops.

beginner

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

A base case is the simplest version of the problem that can be solved directly. It stops the recursion from continuing forever.

intermediate

How does recursion help express problems with nested or hierarchical data?

Recursion naturally breaks down nested or hierarchical data by calling itself on smaller parts, matching the structure of the data.

Which of these problems is best solved using recursion?

A Summing numbers from 1 to n

B Finding factorial of a number

C Printing numbers from 1 to 10

D Adding two numbers

Factorial calculation naturally fits recursion because it breaks down into smaller factorial problems.

What stops a recursive function from running forever?

A Function parameters

B Loop condition

C Return statement

D Base case

The base case defines when recursion should stop by solving the simplest problem directly.

Which of these is NOT a reason to use recursion?

A To avoid using any loops

B To handle nested data structures

C To simplify complex problems

D To express divide and conquer algorithms

Recursion is not used just to avoid loops; loops are useful and sometimes better for simple repetitive tasks.

Loops struggle to express problems that are:

A Nested or hierarchical

B Fixed number of iterations

C Simple arithmetic

D Linear and repetitive

Nested or hierarchical problems are cleaner to express with recursion than with loops.

What is a key difference between loops and recursion?

A Loops always use more memory than recursion

B Loops use function calls, recursion does not

C Recursion breaks problems into smaller parts, loops repeat steps

D Recursion cannot solve repetitive tasks

Recursion solves problems by breaking them down, while loops repeat the same steps until a condition is met.

Explain why recursion is useful for problems that loops cannot express cleanly.

Think about how recursion matches the problem's structure.

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

Base case is like a stopping point.

Practice

1. Why do we use recursion instead of loops in some problems?

easy

A. Because recursion can express problems with self-similar structure more naturally

B. Because loops are slower than recursion in all cases

C. Because recursion uses less memory than loops always

D. Because loops cannot repeat any actions

Solution

1. Step 1: Understand problem structure

   Some problems have parts that look like smaller versions of themselves, like trees or nested lists.

2. Step 2: Compare recursion and loops

   Loops repeat actions linearly, but recursion can call itself to handle nested or self-similar parts easily.

3. Final Answer:

   Because recursion can express problems with self-similar structure more naturally -> Option A

4. Quick Check:

   Self-similar problems naturally use recursion [OK]

Hint: Recursion fits nested/self-similar problems better [OK]

Common Mistakes:

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

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

easy

A. void func() { func(); }

B. void func() { if(condition) func(); else return; }

C. void func() { for(int i=0; i<10; i++) func(); }

D. void func() { while(true) func(); }

Solution

1. Step 1: Identify base case in recursion

   Recursive functions must have a condition to stop calling themselves to avoid infinite loops.

2. Step 2: Check options for base case

   void func() { if(condition) func(); else return; } has an if condition that stops recursion; others either lack base case or use loops incorrectly.

3. Final Answer:

   void func() { if(condition) func(); else return; } -> Option B

4. Quick Check:

   Recursive functions must have base case [OK]

Hint: Look for base case to stop recursion [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Confusing loops with recursion calls
• Using infinite loops inside recursive functions

3. What is the output of the following C++ code?

#include <iostream>
int factorial(int n) {
  if (n == 0) return 1;
  else return n * factorial(n - 1);
}

int main() {
  std::cout << factorial(4);
  return 0;
}

medium

A. 16

B. 10

C. 120

D. 24

Solution

1. Step 1: Understand factorial recursion

   factorial(4) = 4 * factorial(3), factorial(3) = 3 * factorial(2), and so on until factorial(0) = 1.

2. Step 2: Calculate factorial(4)

   factorial(4) = 4 * 3 * 2 * 1 = 24.

3. Final Answer:

   24 -> Option D

4. Quick Check:

   4! = 24 [OK]

Hint: Recall factorial definition: n! = n*(n-1)! [OK]

Common Mistakes:

• Confusing factorial with sum
• Forgetting base case returns 1
• Multiplying incorrectly

4. Find the error in this recursive function that tries to sum numbers from n down to 1:

int sum(int n) {
  if (n == 0) return 0;
  else return n + sum(n);
}

medium

A. Recursive call uses sum(n) instead of sum(n - 1)

B. Missing base case for n == 1

C. Function should return n * sum(n - 1)

D. No error, function works correctly

Solution

1. Step 1: Check recursive call argument

   The function calls sum(n) again without decreasing n, causing infinite recursion.

2. Step 2: Correct recursive call

   It should call sum(n - 1) to reduce n each time and reach base case.

3. Final Answer:

   Recursive call uses sum(n) instead of sum(n - 1) -> Option A

4. Quick Check:

   Recursion requires decreasing argument [OK]

Hint: Recursive call must reduce problem size [OK]

Common Mistakes:

• Calling recursion with same argument causing infinite loop
• Confusing sum with product
• Missing base case

5. You want to print all paths from root to leaves in a tree structure. Why is recursion better than loops for this task?

hard

A. Because loops cannot access tree nodes

B. Because recursion uses less CPU than loops

C. Because loops cannot handle multiple branching paths easily

D. Because recursion always runs faster than loops

Solution

1. Step 1: Understand tree traversal

   Printing all root-to-leaf paths requires exploring multiple branches at each node.

2. Step 2: Compare recursion and loops for branching

   Loops handle linear repetition well but struggle with multiple branches; recursion naturally explores each branch by calling itself.

3. Final Answer:

   Because loops cannot handle multiple branching paths easily -> Option C

4. Quick Check:

   Recursion naturally handles branching [OK]

Hint: Recursion handles branching paths naturally [OK]

Common Mistakes:

• Thinking loops can easily replace recursion for trees
• Assuming recursion is always faster
• Believing loops cannot access nodes