Lab 1: Recursion

In this lab, we will explore recursion and its applications in algorithm design. We will implement a specific problem using both recursive and non-recursive methods, analyze their time and space complexities, and provide code examples in Python, C++, and JavaScript.

We’ve chosen the factorial function as our example problem, which is a classic case for demonstrating recursion.

We demonstrate both:

• Recursive implementation (direct application of definition)
• Non-recursive (iterative) implementation (using loops)

Mathematical Definition:

Let $n \in \mathbb{Z}, n \geq 0$

Implementation

# Recursive factorial
def factorial_recursive(n):
    if n == 0:
        return 1
    return n * factorial_recursive(n - 1)
 
# Iterative factorial
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result
 
# Driver
n = 5
print("Recursive:", factorial_recursive(n))
print("Iterative:", factorial_iterative(n))

#include <iostream>
using namespace std;
 
// Recursive factorial
int factorial_recursive(int n) {
    if (n == 0)
        return 1;
    return n * factorial_recursive(n - 1);
}
 
// Iterative factorial
int factorial_iterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; ++i)
        result *= i;
    return result;
}
 
int main() {
    int n = 5;
    cout << "Recursive: " << factorial_recursive(n) << endl;
    cout << "Iterative: " << factorial_iterative(n) << endl;
    return 0;
}

// Recursive factorial
function factorial_recursive(n) {
  if (n === 0) return 1;
  return n * factorial_recursive(n - 1);
}
 
// Iterative factorial
function factorial_iterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}
 
// Driver
const n = 5;
console.log("Recursive:", factorial_recursive(n));
console.log("Iterative:", factorial_iterative(n));

Expected Output

When you run the above code for $n = 5$, you should see the following output:

Recursive: 120
Iterative: 120

Time and Space Complexity Analysis

Sure. Here’s the content reformatted in Markdown for your documentation or study notes.

Practice

LeetCode

• Fibonacci Number - LeetCode #509  A classic recurrence-based problem. Implement using both naive recursion and optimized bottom-up (iterative) dynamic programming.

• Reverse String - LeetCode #344  Can be solved recursively by swapping characters from both ends inward, or iteratively using a two-pointer loop.

• Running Sum of 1d Array - LeetCode #1480  A basic prefix-sum problem. Try recursive accumulation with base case + recursion, and compare to standard loop-based summing.

• Clumsy Factorial - LeetCode #1006  A math-based variant of the factorial problem. Useful for exploring recursion vs stack vs simulation.

• Factorial Trailing Zeroes - LeetCode #172  Although not recursive itself, it provides an interesting exploration of the factorial function and powers of 5.

• Power of Two - LeetCode #231  A simple recursive/iterative check for powers of 2. Try solving recursively and compare to bit manipulation or loop-based methods.

CodeChef

• Factorial - RECUR03  Simple recursive factorial implementation. Perfect starter problem.

• Sum of N Natural Numbers - RECUR02  Use recursion to sum $1 + 2 + \ldots + n$. Easy to compare against loop-based approach.

• Fibonacci Numbers - RECUR04V  Classic recursion-vs-iteration practice problem. Enables discussion of exponential time vs memoized recursion.

References

1. Python Official Documentation 

2. C++ Reference 

3. JavaScript MDN 

4. C++ Standard Template Library 

5. CS50x Week 3: Algorithms. (2025). Harvard University. Retrieved from https://cs50.harvard.edu/x/2025/weeks/3/ 

6. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.
   Introduction to Algorithms, 3rd/4th Edition, MIT Press.