Why Recursion Exists and What Loops Cannot Express Cleanly in DSA C - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to make the function call itself recursively.

DSA C

void countdown(int n) {
    if (n <= 0) {
        printf("Blastoff!\n");
        return;
    }
    printf("%d\n", n);
    countdown([1]);
}

Drag options to blanks, or click blank then click option'

An - 1

Bn + 1

Cn * 2

Dn / 2

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 causes infinite recursion.

Using n * 2 or n / 2 does not count down properly.

The function calls itself with n - 1 to count down until it reaches zero.

2fill in blank

medium

Complete the code to calculate factorial using recursion.

DSA C

int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial([1]);
}

Drag options to blanks, or click blank then click option'

An * 2

Bn + 1

Cn - 1

Dn / 2

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 causes infinite recursion.

Using n * 2 or n / 2 does not compute factorial correctly.

Factorial of n is n times factorial of n - 1, reducing n each call.

3fill in blank

hard

Fix the error in the recursive Fibonacci function call.

DSA C

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci([1]);
}

Drag options to blanks, or click blank then click option'

An - 2

Bn - 1

Cn + 1

Dn * 2

Attempts:

3 left

💡 Hint

Common Mistakes

Using n - 1 twice causes incorrect results.

Using n + 1 or n * 2 causes errors or infinite recursion.

Fibonacci is sum of fibonacci(n-1) and fibonacci(n-2).

4fill in blank

hard

Fill both blanks to create a recursive function that sums numbers from n down to 1.

DSA C

int sum_to_n(int n) {
    if (n == 0) {
        return 0;
    }
    return n [1] sum_to_n(n [2] 1);
}

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication or division instead of addition.

Not reducing n in the recursive call.

Sum is n plus sum of numbers from n-1 down to 1.

5fill in blank

hard

Fill all three blanks to create a recursive function that prints numbers from 1 to n.

DSA C

void print_ascending(int n) {
    if (n == 0) {
        return;
    }
    print_ascending([1]);
    printf("%d\n", [2]);
    [3];
}

Drag options to blanks, or click blank then click option'

An - 1

Bn

Creturn

Dn + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Calling with n + 1 causes infinite recursion.

Not returning after printing causes unexpected behavior.

The function calls itself with n-1, then prints n, then returns.

Practice

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

easy

A. Because loops cannot be written in C language

B. Because loops are slower than recursion in all cases

C. Because recursion can express problems with self-similar structure more clearly

D. Because recursion uses less memory than loops

Solution

1. Step 1: Understand recursion's purpose

   Recursion is used to solve problems that can be broken down into smaller similar problems, like tree traversals or factorial calculation.

2. Step 2: Compare recursion and loops

   Loops are good for repeated actions but cannot easily express problems with nested or self-similar structure without complex code.

3. Final Answer:

   Because recursion can express problems with self-similar structure more clearly -> Option C

4. Quick Check:

   Recursion clarity = Because recursion can express problems with self-similar structure more clearly [OK]

Hint: Recursion fits self-similar problems better than loops [OK]

Common Mistakes:

• Thinking loops are always faster than recursion
• Believing recursion always uses less memory
• Assuming loops cannot be written in C

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

easy

A. int factorial(int n) { for (int i = 1; i <= n; i++) return i * factorial(i - 1); }

B. int factorial(int n) { while (n > 0) return n * factorial(n - 1); }

C. int factorial(int n) { if (n == 1) return 0; else return n + factorial(n - 1); }

D. int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); }

Solution

1. Step 1: Check base case correctness

   int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } correctly returns 1 when n is 0, which is the factorial base case.

2. Step 2: Check recursive call and return

   int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } multiplies n by factorial(n-1), correctly defining factorial recursively.

3. Final Answer:

   int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } -> Option D

4. Quick Check:

   Correct factorial recursion syntax = int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } [OK]

Hint: Look for correct base case and recursive call [OK]

Common Mistakes:

• Missing base case or wrong base case
• Using loops inside recursive function incorrectly
• Returning wrong values in base case

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

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

int main() {
  printf("%d", sum(3));
  return 0;
}

medium

A. 3

B. 6

C. 0

D. Compilation error

Solution

1. Step 1: Trace recursive calls for sum(3)

   sum(3) = 3 + sum(2), sum(2) = 2 + sum(1), sum(1) = 1 + sum(0), sum(0) = 0.

2. Step 2: Calculate total sum

   sum(3) = 3 + 2 + 1 + 0 = 6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   1+2+3 = 6 [OK]

Hint: Add numbers from n down to 0 recursively [OK]

Common Mistakes:

• Confusing sum with multiplication
• Forgetting base case returns 0
• Assuming sum(3) returns 3 only

4. Find the error in this recursive function to compute Fibonacci numbers:

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

int main() {
  printf("%d", fib(4));
  return 0;
}

medium

A. No error; function works correctly

B. Missing base case for n == 2

C. Function causes infinite recursion

D. Incorrect return type

Solution

1. Step 1: Check base cases

   Base cases for n == 0 and n == 1 are correctly defined.

2. Step 2: Verify recursive calls

   Function returns fib(n-1) + fib(n-2), which is correct Fibonacci definition.

3. Final Answer:

   No error; function works correctly -> Option A

4. Quick Check:

   Fibonacci recursion correct = No error; function works correctly [OK]

Hint: Check base cases and recursive formula carefully [OK]

Common Mistakes:

• Thinking base case for n==2 is needed
• Assuming infinite recursion without base cases
• Confusing return types

5. Which problem below is best solved using recursion rather than loops, and why?

• A) Calculating the sum of numbers from 1 to n
• B) Traversing a directory tree to list all files
• C) Printing numbers from 1 to 10
• D) Repeating a task 5 times

hard

A. Traversing directory tree because recursion handles nested structures naturally

B. Calculating sum because recursion is faster than loops

C. Printing numbers because recursion is simpler than loops here

D. Repeating a task because recursion uses less memory

Solution

1. Step 1: Analyze problem types

   Sum, printing, and repeating tasks are simple linear problems suited for loops.

2. Step 2: Identify nested structure problem

   Directory trees have nested folders and files, which recursion can explore naturally by calling itself on subfolders.

3. Final Answer:

   Traversing directory tree because recursion handles nested structures naturally -> Option A

4. Quick Check:

   Nested structures = recursion best = Traversing directory tree because recursion handles nested structures naturally [OK]

Hint: Use recursion for nested or self-similar data structures [OK]

Common Mistakes:

• Choosing loops for nested tree traversal
• Assuming recursion is always faster
• Confusing simple repetition with recursion need