9일차: 반복 vs 재귀: 성능 분석 (팩토리얼)

Source: Dev.to

Recursion vs. Iteration

재귀는 종종 코드를 더 깔끔하게 작성할 수 있고 읽기 쉬우며(특히 트리 구조에서), 하지만 비용이 있습니다: 공간 복잡도.

• 반복은 단일 스택 프레임을 사용합니다; 루프 안에서 변수를 단순히 업데이트합니다.
  공간: (O(1))

• 재귀는 (N) 개의 스택 프레임을 사용합니다. 예를 들어 factorial(10000)을 계산하면 메모리에 10,000개의 프레임이 쌓입니다.
  공간: (O(N))

재귀 깊이가 너무 커지면 스택 오버플로우로 프로그램이 충돌할 수 있지만, 반복 루프는 무한히 계속될 수 있습니다.

Implementation in C

// Day 9: The Two Paths
#include 

// Method 1: Recursive (The Elegant Way)
// Risks: Stack overflow for large numbers
unsigned long long factorial_rec(int n) {
    if (n
}