Why Recursion Exists and What Loops Cannot Express Cleanly in DSA C - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive vs Loop Factorial

What is the output of the following C code that calculates factorial using recursion and a loop?

DSA C

#include <stdio.h>

int factorial_recursive(int n) {
    if (n <= 1) return 1;
    return n * factorial_recursive(n - 1);
}

int factorial_loop(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

int main() {
    int n = 4;
    printf("%d %d\n", factorial_recursive(n), factorial_loop(n));
    return 0;
}

A 120 120

B 24 120

C 24 24

D 120 24

💡 Hint

Trace factorial of 4: 4*3*2*1 = 24

Both recursive and loop functions correctly compute factorial of 4, which is 24.

🧠 Conceptual

intermediate

Why Recursion Can Express Tree Traversals Cleanly

Which of the following best explains why recursion is preferred over loops for tree traversals?

A Recursion naturally handles branching structures by calling itself for each child node, which loops cannot do cleanly without extra data structures.

B Loops are faster and use less memory than recursion for tree traversals.

C Loops can only traverse linear data structures, not trees.

D Recursion uses iteration internally, so it is just a fancy loop.

💡 Hint

Think about how trees have multiple branches at each node.

Recursion allows a function to call itself for each child node, naturally matching the tree's branching structure. Loops would require explicit stacks or queues to track nodes.

🔧 Debug

advanced

Identify the Error in Recursive Fibonacci Implementation

What error will the following C code produce when run?

DSA C

#include <stdio.h>

int fib(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else return fib(n - 1) + fib(n - 2);
}

int main() {
    int result = fib(-1);
    printf("%d\n", result);
    return 0;
}

A Compilation error

B Prints 0

C Prints 1

D Stack overflow due to infinite recursion

💡 Hint

Consider what happens when n is negative.

The function does not handle negative inputs, so fib(-1) calls fib(-2) and fib(-3) endlessly, causing stack overflow.

🚀 Application

advanced

Using Recursion to Generate All Subsets

Which output correctly shows all subsets of {1, 2} generated by this recursive function?

DSA C

#include <stdio.h>

void subsets(int arr[], int n, int index, int subset[], int subset_size) {
    if (index == n) {
        printf("{");
        for (int i = 0; i < subset_size; i++) {
            printf("%d", subset[i]);
            if (i < subset_size - 1) printf(", ");
        }
        printf("}\n");
        return;
    }
    // Include current element
    subset[subset_size] = arr[index];
    subsets(arr, n, index + 1, subset, subset_size + 1);
    // Exclude current element
    subsets(arr, n, index + 1, subset, subset_size);
}

int main() {
    int arr[] = {1, 2};
    int subset[2];
    subsets(arr, 2, 0, subset, 0);
    return 0;
}

A {1, 2} {1} {2} {}

B {1} {2} {1, 2} {}

C {} {1} {2} {1, 2}

D {} {2} {1} {1, 2}

💡 Hint

Full set first (include-include), then {1} (include-exclude), {2} (exclude-include), {} (exclude-exclude).

The function prints subsets starting with {1, 2}, then {1}, then {2}, then {} in that order.

🧠 Conceptual

expert

Why Some Problems Cannot Be Expressed Cleanly with Loops Alone

Which statement best explains why certain problems require recursion instead of loops?

A Loops are always slower and less memory efficient than recursion.

B Some problems have self-similar structures that require the function to call itself with smaller inputs, which loops cannot represent without extra data structures.

C Loops cannot perform repeated actions, only recursion can.

D Recursion is the only way to write any algorithm in a functional style.

💡 Hint

Think about problems like traversing nested folders or trees.

Recursion naturally fits problems where the solution involves solving smaller instances of the same problem, like nested or hierarchical data, which loops alone cannot express cleanly.