Recursion vs Iteration When Each Wins in DSA C - Build Both Approaches

Recursion vs Iteration: When Each Wins

📖 Scenario: Imagine you are helping a friend understand two ways to solve problems: recursion and iteration. You will create simple C programs to see how each method works and when one might be better than the other.

🎯 Goal: Build two C functions to calculate the factorial of a number: one using recursion and one using iteration. Then compare their outputs for the same input.

📋 What You'll Learn

Create a variable called number with the value 5

Write a recursive function called factorial_recursive that takes an int n and returns the factorial of n

Write an iterative function called factorial_iterative that takes an int n and returns the factorial of n

Print the results of both functions for the variable number

💡 Why This Matters

🌍 Real World

Understanding recursion and iteration helps solve many programming problems like searching, sorting, and navigating data structures.

💼 Career

Many software jobs require knowing when to use recursion or iteration for efficient and clear code.

1

Create the input variable

Create an integer variable called number and set it to 5.

DSA C

#include 

int main() {
    // Create an integer variable called number and set it to 5
    // Your code here

    return 0;
}

Hint

Use int number = 5; inside the main function.

2

Write the recursive factorial function

Write a recursive function called factorial_recursive that takes an integer n and returns the factorial of n. Use the base case if (n == 0) to return 1, else return n * factorial_recursive(n - 1).

DSA C

#include 

// Write the recursive factorial function here
// Your code here

int main() {
    int number = 5;

    return 0;
}

Hint

Remember the base case for factorial is when n == 0.

3

Write the iterative factorial function

Write an iterative function called factorial_iterative that takes an integer n and returns the factorial of n. Use a for loop to multiply numbers from 1 to n.

DSA C

#include 

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

// Write the iterative factorial function here
// Your code here

int main() {
    int number = 5;

    return 0;
}

Hint

Use a for loop from 1 to n multiplying a result variable.

4

Print the factorial results

Print the factorial of number using both factorial_recursive and factorial_iterative functions. Use printf to show the results with labels.

DSA C

#include 

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

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

int main() {
    int number = 5;

    // Print the factorial results using both functions
    // Your code here

    return 0;
}

Hint

Use printf with the format "Recursive factorial of %d is %d\n" and call factorial_recursive(number). Do the same for factorial_iterative.

Practice

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

easy

A. When you want to avoid function calls

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

C. When memory usage must be minimal

D. When the problem requires simple repeated loops

Solution

1. Step 1: Understand recursion use case

   Recursion works well when a problem breaks down into smaller similar problems, like factorial or tree traversal.

2. Step 2: Compare with iteration use cases

   Iteration is better for simple repeated loops without breaking problems into smaller parts.

3. Final Answer:

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

4. Quick Check:

   Recursion = divide and conquer [OK]

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

Common Mistakes:

• Thinking recursion is always better for memory
• Confusing iteration as better for divide-and-conquer
• Ignoring function call overhead in recursion

2. Which of the following is the correct syntax for a recursive function in C?

easy

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

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

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

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

Solution

1. Step 1: Identify recursive call with base condition

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

2. Step 2: Check options for base condition

   void func() { if(condition) func(); } calls itself only if a condition is true, which is correct recursive syntax.

3. Final Answer:

   void func() { if(condition) func(); } -> Option A

4. Quick Check:

   Recursive call inside condition = void func() { if(condition) func(); } [OK]

Hint: Recursive calls need a stopping condition [OK]

Common Mistakes:

• Missing base condition causing infinite recursion
• Using loops instead of conditional recursion
• Confusing infinite loops with recursion

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

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

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

medium

A. 24

B. 10

C. 120

D. Error: infinite recursion

Solution

1. Step 1: Trace factorial(4) calls

   factorial(4) calls factorial(3), factorial(3) calls factorial(2), factorial(2) calls factorial(1), factorial(1) calls factorial(0) which returns 1.

2. Step 2: Calculate return values

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

3. Final Answer:

   24 -> Option A

4. Quick Check:

   4! = 24 [OK]

Hint: Factorial recursion multiplies down to 1 [OK]

Common Mistakes:

• Confusing factorial(4) with sum 1+2+3+4
• Forgetting base case returns 1
• Assuming infinite recursion error

4. Identify the error in this recursive function that calculates the sum of numbers from 1 to n:

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

medium

A. Return type should be void

B. Missing base case

C. Recursive call uses same argument causing infinite recursion

D. Function should use iteration instead

Solution

1. Step 1: Check base case correctness

   The base case is correct: if n == 0, return 0.

2. Step 2: Analyze recursive call argument

   The recursive call uses sum(n) instead of sum(n-1), so it calls itself with the same argument endlessly causing infinite recursion.

3. Final Answer:

   Recursive call uses same argument causing infinite recursion -> Option C

4. Quick Check:

   Recursive argument must change to avoid infinite calls [OK]

Hint: Recursive calls must progress toward base case [OK]

Common Mistakes:

• Ignoring argument change in recursive call
• Thinking base case alone stops recursion
• Confusing return type with recursion correctness

5. You need to process a large dataset with limited memory. Which approach is better and why?

// Approach 1: Recursive traversal
void process(int n) {
  if (n == 0) return;
  process(n-1);
  printf("%d ", n);
}

// Approach 2: Iterative traversal
void process_iter(int n) {
  for (int i = 1; i <= n; i++) {
    printf("%d ", i);
  }
}

hard

A. Recursive is better because it uses less memory

B. Both are equally good for memory

C. Neither works for large datasets

D. Iterative is better because recursion uses stack memory for calls

Solution

1. Step 1: Analyze memory usage of recursion

   Recursive calls add stack frames for each call, increasing memory usage proportional to n.

2. Step 2: Analyze iteration memory usage

   Iteration uses a fixed amount of memory for loop variables, so it uses less memory overall.

3. Final Answer:

   Iterative is better because recursion uses stack memory for calls -> Option D

4. Quick Check:

   Iteration uses less memory than recursion [OK]

Hint: Iteration avoids stack overhead of recursion [OK]

Common Mistakes:

• Assuming recursion always uses less memory
• Ignoring stack overflow risk in recursion
• Thinking iteration uses more memory due to loops