← Back to DSA Course | Chapter 1: Introduction & Complexity | Lesson 6 of 6

Recursion vs Iteration

In this page:

  1. Basic Difference
  2. Factorial
  3. Sum of Numbers
  4. Memory Difference
  5. When to Use Which

Basic Difference

Recursion solves a problem by having a function call itself on smaller subproblems, while iteration solves it by repeating a block of code in a loop until a condition is met. Both can implement the exact same logic; they just structure the repetition differently.

Example: Basic Difference

#include <iostream>
using namespace std;
int factRecursive(int n) {
    if (n <= 1) return 1;
    return n * factRecursive(n - 1);
}
int factIterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}
int main() {
    cout << "Recursive: " << factRecursive(5) << ", Iterative: " << factIterative(5) << endl;
    return 0;
}
public class Main {
    static int factRecursive(int n) {
        if (n <= 1) return 1;
        return n * factRecursive(n - 1);
    }
    static int factIterative(int n) {
        int result = 1;
        for (int i = 2; i <= n; i++) result *= i;
        return result;
    }
    public static void main(String[] args) {
        System.out.println("Recursive: " + factRecursive(5) + ", Iterative: " + factIterative(5));
    }
}
def fact_recursive(n):
    if n <= 1:
        return 1
    return n * fact_recursive(n - 1)

def fact_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print("Recursive:", fact_recursive(5), ", Iterative:", fact_iterative(5))
#include <stdio.h>
int factRecursive(int n) {
    if (n <= 1) return 1;
    return n * factRecursive(n - 1);
}
int factIterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}
int main() {
    printf("Recursive: %d, Iterative: %d\n", factRecursive(5), factIterative(5));
    return 0;
}

Factorial

Computing a factorial recursively multiplies n by factorial(n-1) down to a base case of 1, which reads almost like the mathematical definition. The iterative version uses a loop and an accumulator variable, and does the same multiplications without any function-call overhead.

Example: Factorial

#include <iostream>
using namespace std;
int factorial(int n) {
    if (n <= 1) return 1; // base case
    return n * factorial(n - 1);
}
int main() {
    cout << "factorial(6): " << factorial(6) << endl;
    return 0;
}
public class Main {
    static int factorial(int n) {
        if (n <= 1) return 1; // base case
        return n * factorial(n - 1);
    }
    public static void main(String[] args) {
        System.out.println("factorial(6): " + factorial(6));
    }
}
def factorial(n):
    if n <= 1:  # base case
        return 1
    return n * factorial(n - 1)

print("factorial(6):", factorial(6))
#include <stdio.h>
int factorial(int n) {
    if (n <= 1) return 1; /* base case */
    return n * factorial(n - 1);
}
int main() {
    printf("factorial(6): %d\n", factorial(6));
    return 0;
}

Sum of Numbers

Summing a list of numbers is another problem solvable both ways: recursively add the first element to the sum of the rest, or iteratively add each element to a running total in a loop. The results are identical, but the recursive version uses more memory per element processed.

Example: Sum of Numbers

#include <iostream>
using namespace std;
int sumRecursive(int arr[], int n) {
    if (n == 0) return 0;
    return arr[n - 1] + sumRecursive(arr, n - 1);
}
int sumIterative(int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) total += arr[i];
    return total;
}
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    cout << "Recursive: " << sumRecursive(arr, 5) << ", Iterative: " << sumIterative(arr, 5) << endl;
    return 0;
}
public class Main {
    static int sumRecursive(int[] arr, int n) {
        if (n == 0) return 0;
        return arr[n - 1] + sumRecursive(arr, n - 1);
    }
    static int sumIterative(int[] arr) {
        int total = 0;
        for (int x : arr) total += x;
        return total;
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println("Recursive: " + sumRecursive(arr, arr.length) + ", Iterative: " + sumIterative(arr));
    }
}
def sum_recursive(arr):
    if not arr:
        return 0
    return arr[0] + sum_recursive(arr[1:])

def sum_iterative(arr):
    total = 0
    for x in arr:
        total += x
    return total

arr = [1, 2, 3, 4, 5]
print("Recursive:", sum_recursive(arr), ", Iterative:", sum_iterative(arr))
#include <stdio.h>
int sumRecursive(int arr[], int n) {
    if (n == 0) return 0;
    return arr[n - 1] + sumRecursive(arr, n - 1);
}
int sumIterative(int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) total += arr[i];
    return total;
}
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    printf("Recursive: %d, Iterative: %d\n", sumRecursive(arr, 5), sumIterative(arr, 5));
    return 0;
}

Memory Difference

Iteration generally uses a small, constant amount of extra memory (just loop variables), while recursion consumes stack space proportional to its depth, since each call stays on the stack until it returns. For very deep recursion, this can matter a lot for performance and even correctness.

Example: Memory Difference

#include <iostream>
using namespace std;
int sumRecursive(int n) {
    if (n == 0) return 0; // uses stack space proportional to depth: O(n)
    return n + sumRecursive(n - 1);
}
int sumIterative(int n) {
    int total = 0; // constant extra memory: O(1)
    for (int i = 1; i <= n; i++) total += i;
    return total;
}
int main() {
    cout << "Recursive (O(n) space): " << sumRecursive(5) << endl;
    cout << "Iterative (O(1) space): " << sumIterative(5) << endl;
    return 0;
}
public class Main {
    static int sumRecursive(int n) {
        if (n == 0) return 0; // O(n) stack space
        return n + sumRecursive(n - 1);
    }
    static int sumIterative(int n) {
        int total = 0; // O(1) space
        for (int i = 1; i <= n; i++) total += i;
        return total;
    }
    public static void main(String[] args) {
        System.out.println("Recursive (O(n) space): " + sumRecursive(5));
        System.out.println("Iterative (O(1) space): " + sumIterative(5));
    }
}
def sum_recursive(n):
    if n == 0:
        return 0  # O(n) stack space
    return n + sum_recursive(n - 1)

def sum_iterative(n):
    total = 0  # O(1) space
    for i in range(1, n + 1):
        total += i
    return total

print("Recursive (O(n) space):", sum_recursive(5))
print("Iterative (O(1) space):", sum_iterative(5))
#include <stdio.h>
int sumRecursive(int n) {
    if (n == 0) return 0; /* O(n) stack space */
    return n + sumRecursive(n - 1);
}
int sumIterative(int n) {
    int total = 0; /* O(1) space */
    for (int i = 1; i <= n; i++) total += i;
    return total;
}
int main() {
    printf("Recursive (O(n) space): %d\n", sumRecursive(5));
    printf("Iterative (O(1) space): %d\n", sumIterative(5));
    return 0;
}

When to Use Which

Choose recursion when it makes the problem's structure clearer, such as trees or divide-and-conquer, and choose iteration when performance or stack depth is a concern, such as processing very large flat lists. Many languages let you convert one into the other when needed.

Example: When to Use Which

#include <iostream>
using namespace std;
// Recursion: clearer for naturally nested structure, like tree depth.
int treeDepth(int nodes[], int i, int n) {
    if (i >= n) return 0;
    int left = treeDepth(nodes, 2 * i + 1, n);
    int right = treeDepth(nodes, 2 * i + 2, n);
    return 1 + max(left, right);
}
int main() {
    int nodes[] = {1, 2, 3, 4, 5, 6, 7};
    cout << "Tree depth (recursion fits naturally): " << treeDepth(nodes, 0, 7) << endl;
    return 0;
}
public class Main {
    // Recursion: clearer for naturally nested structure, like tree depth.
    static int treeDepth(int[] nodes, int i, int n) {
        if (i >= n) return 0;
        int left = treeDepth(nodes, 2 * i + 1, n);
        int right = treeDepth(nodes, 2 * i + 2, n);
        return 1 + Math.max(left, right);
    }
    public static void main(String[] args) {
        int[] nodes = {1, 2, 3, 4, 5, 6, 7};
        System.out.println("Tree depth (recursion fits naturally): " + treeDepth(nodes, 0, 7));
    }
}
# Recursion: clearer for naturally nested structure, like tree depth.
def tree_depth(nodes, i, n):
    if i >= n:
        return 0
    left = tree_depth(nodes, 2 * i + 1, n)
    right = tree_depth(nodes, 2 * i + 2, n)
    return 1 + max(left, right)

nodes = [1, 2, 3, 4, 5, 6, 7]
print("Tree depth (recursion fits naturally):", tree_depth(nodes, 0, 7))
#include <stdio.h>
int maxInt(int a, int b) { return a > b ? a : b; }
int treeDepth(int nodes[], int i, int n) {
    if (i >= n) return 0;
    int left = treeDepth(nodes, 2 * i + 1, n);
    int right = treeDepth(nodes, 2 * i + 2, n);
    return 1 + maxInt(left, right);
}
int main() {
    int nodes[] = {1, 2, 3, 4, 5, 6, 7};
    printf("Tree depth (recursion fits naturally): %d\n", treeDepth(nodes, 0, 7));
    return 0;
}
🔒

Chapter Quiz — Complete all 6 topics to unlock

0/6 topics done

Complete these topics first:

← Previous Lesson Recursion Basics Next Lesson → Array Introduction

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.