반복문과 재귀함수

반복문 (Loop)

반복문의 개념

• 동일한 코드를 여러 번 실행할 때 사용.
• 파이썬에서는 for, while 두 가지 문법이 기본.
• 조건이 True인 동안 계속 반복 수행.

for 문 기본 구조

for 변수 in 반복가능한_객체:
    실행할_코드

for i in range(5):
    print(i)  # 0부터 4까지 출력

while 문 기본 구조

while 조건:
    실행할_코드

i = 0
while i < 5:
    print(i)
    i += 1

중첩 반복문

• 반복문 안에 또 다른 반복문을 사용하는 형태
• 완전탐색(브루트포스) 문제에서 자주 활용됨

for i in range(3):
    for j in range(2):
        print(i, j)

반복문의 시간 복잡도

구조	시간 복잡도
단일 반복문	O(N)
이중 반복문	O(N²)
삼중 반복문	O(N³)

---

재귀 함수 (Recursion)

재귀 함수의 개념

• 함수가 자기 자신을 다시 호출하는 방식.
• 복잡한 문제를 작게 나누어 처리할 수 있음.
• 반드시 종료 조건(Base Case)이 필요함.

기본 구조

def func():
    if 종료조건:
        return 결과
    else:
        return func()

팩토리얼 예시

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

재귀 함수의 동작 원리

• 함수가 스택에 쌓이며 호출되고, 종료 조건을 만나면 거꾸로 결과를 반환하며 정리된다.
• 메모리 구조상 스택(stack) 을 사용하며, 깊이가 너무 깊어지면 RecursionError 발생 가능.

---

반복문 vs 재귀 함수 비교

항목	반복문	재귀 함수
구조	명시적 반복	함수 내부에서 자기 자신 호출
종료 조건	명확한 반복 조건	종료 조건(base case) 필요
메모리	적게 사용	함수 호출 스택 사용
속도	일반적으로 빠름	느릴 수 있음
사용 예시	합계, 누적 계산 등	DFS, 분할정복, 트리 탐색 등

---

예제 : 1부터 N까지 합 구하기

for문

def sum_loop(n):
    total = 0
    for i in range(1, n+1):
        total += i
    return total

재귀함수

def sum_rec(n):
    if n == 0:
        return 0
    return n + sum_rec(n - 1)

---

피보나치 수열 (재귀)

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

• 중복 호출이 많아 성능이 비효율적.
• 향후 동적 프로그래밍(DP) 또는 메모이제이션으로 개선 가능.

---

핵심 요약

• 반복문은 조건을 만족하는 동안 반복 실행되는 구조.
• 재귀 함수는 동일한 문제를 더 작은 문제로 쪼개 자기 자신을 호출하여 해결.
• 재귀는 구현이 간단해질 수 있으나, 메모리와 성능에 주의가 필요.
• 알고리즘 문제 풀이 시 반복과 재귀 중 적절한 방식 선택이 중요하다.

---

재귀는 DFS, 백트래킹, 분할정복, 트리 탐색과 같은 고급 알고리즘에서 재귀 함수는 필수 도구로 사용된다.