Why Recursion Exists and What Loops Cannot Express Cleanly in DSA C++ - See It Work

Why Recursion Exists and What Loops Cannot Express Cleanly

📖 Scenario: Imagine you are organizing a family reunion. Each person might have children, and those children might have their own children, and so on. You want to list every family member starting from the oldest ancestor down to the youngest generation.This kind of family tree can be tricky to list using simple loops because the number of generations is not fixed and can vary for each branch.

🎯 Goal: You will build a simple family tree using nested structures and use recursion to print all family members. This will show why recursion is useful when loops alone cannot easily handle such nested, unknown-depth data.

📋 What You'll Learn

Create a struct called Person with a string name and a vector<Person> children

Create a Person variable called grandparent with the name "Grandpa Joe" and two children

Add a helper function called printFamily that takes a Person and prints the name and recursively prints all children with indentation

Call printFamily on grandparent to display the full family tree

💡 Why This Matters

🌍 Real World

Family trees, organizational charts, file system directories, and many other hierarchical data structures require recursion to process cleanly.

💼 Career

Understanding recursion is essential for software developers, especially when working with trees, graphs, and nested data formats like JSON or XML.

1

Create the Family Tree Data Structure

Create a struct Person with a string name and a vector<Person> children. Then create a Person variable called grandparent with the name "Grandpa Joe" and two children named "Uncle Bob" and "Aunt Mary" (with no children).

DSA C++

# Define struct Person and create grandparent with two children
// Your code here

Hint

Use struct to define Person. Initialize grandparent with a name and a vector of two children.

2

Add a Helper Function to Print the Family

Add a function called printFamily that takes a const Person& person and an int level (default 0). It should print the person's name with indentation of two spaces per level. Then it should recursively call itself for each child with level + 1.

DSA C++

#include 
#include 
#include 

using namespace std;

struct Person {
    string name;
    vector children;
};

Person grandparent = {"Grandpa Joe", { {"Uncle Bob", {}}, {"Aunt Mary", {}} }};

// Define printFamily function here
// Your code here

int main() {
    return 0;
}

Hint

Use a loop to print spaces for indentation. Then print the person's name. Use recursion to print children with increased level.

3

Call the Recursive Function to Print the Family Tree

Inside main(), call printFamily with grandparent to print the full family tree.

DSA C++

#include 
#include 
#include 

using namespace std;

struct Person {
    string name;
    vector children;
};

Person grandparent = {"Grandpa Joe", { {"Uncle Bob", {}}, {"Aunt Mary", {}} }};

void printFamily(const Person& person, int level = 0) {
    for (int i = 0; i < level; ++i) {
        cout << "  ";
    }
    cout << person.name << endl;
    for (const Person& child : person.children) {
        printFamily(child, level + 1);
    }
}

int main() {
    // Call printFamily here
    // Your code here
}

Hint

Simply call printFamily with grandparent inside main().

4

View the Printed Family Tree Output

Run the program and observe the printed family tree. The output should show Grandpa Joe at the top, then indented Uncle Bob and Aunt Mary below.

DSA C++

#include 
#include 
#include 

using namespace std;

struct Person {
    string name;
    vector children;
};

Person grandparent = {"Grandpa Joe", { {"Uncle Bob", {}}, {"Aunt Mary", {}} }};

void printFamily(const Person& person, int level = 0) {
    for (int i = 0; i < level; ++i) {
        cout << "  ";
    }
    cout << person.name << endl;
    for (const Person& child : person.children) {
        printFamily(child, level + 1);
    }
}

int main() {
    printFamily(grandparent);
    return 0;
}

// Observe the output below

Hint

The output shows the family tree with indentation. Notice how recursion helps print nested children easily.

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