[[OZ코딩스쿨] 초격차 캠프 - 10일차 (함수) Chapter 6-7. 재귀 함수

📌 Python 함수 심화 – Chapter 6-7. 재귀 함수

---

✅ 1. 재귀함수란?

• 재귀함수란 함수 안에서 자신을 다시 호출하는 함수.
• 예시: 팩토리얼
  • 5! = 5 × 4 × 3 × 2 × 1
  • 일반적으로 반복문이나 재귀함수로 구현 가능.

📌 반복문을 이용한 팩토리얼

def oz_factorial(n):
    output = 1
    for i in range(1, n + 1):
        output *= i
    return output

n = int(input("구하고자 하는 팩토리얼의 수를 입력해주세요."))
print(f'{n}의 결과는 {oz_factorial(n)}입니다.')

• 출력

5의 결과는 120입니다.

---

✅ 2. 재귀함수를 이용한 팩토리얼

def oz_factorial(n):
    if n == 0:
        return 1
    else:
        return n * oz_factorial(n - 1)

n = int(input("구하고자 하는 팩토리얼의 수를 입력해주세요."))
print(f'{n}의 결과는 {oz_factorial(n)}입니다.')

• 출력

5의 결과는 120입니다.

---

✅ 3. 재귀함수의 장단점

장점:

• 코드가 간결하고, 문제를 작고 단순한 문제로 나누어 해결 가능.
• 분할 정복이나 트리 구조 같은 문제에서 유용함.

단점:

• 스택 오버플로우 발생 가능성.
• 메모리 사용량 증가 및 속도 저하 가능.
• 중복 계산으로 인해 비효율적인 결과 발생 가능.

🚀 해결 방법

• 꼬리 재귀 최적화: 재귀 호출을 마지막에 위치시키기.
• 메모이제이션(Memoization): 계산된 값을 저장해 중복 계산 방지.
• 동적 계획법(DP): 반복문으로 효율적으로 문제 해결.

---

✅ 4. 재귀함수의 문제점 해결 (피보나치 수열)

📌 메모이제이션 없이 구현

count = 0

def oz_fibo(n):
    global count
    count += 1
    if n == 1 or n == 2:
        return 1
    return oz_fibo(n - 1) + oz_fibo(n - 2)

n = int(input("구하고자 하는 피보나치 수열의 수를 입력해주세요."))
result = oz_fibo(n)
print(f'피보나치 수열 {n}의 값은 {result}이고, 계산된 횟수는 {count}번 입니다.')

• 출력

피보나치 수열 5의 값은 5이고, 계산된 횟수는 9번 입니다.

📌 메모이제이션을 적용한 피보나치 수열

memo = {1: 1, 2: 1}
count = 0

def oz_fibo(n):
    global count
    count += 1
    if n in memo:
        return memo[n]
    memo[n] = oz_fibo(n - 1) + oz_fibo(n - 2)
    return memo[n]

n = int(input("구하고자 하는 피보나치 수열의 수를 입력해주세요."))
result = oz_fibo(n)
print(f'피보나치 수열 {n}의 값은 {result}이고, 계산된 횟수는 {count}번 입니다.')

• 출력

피보나치 수열 10의 값은 55이고, 계산된 횟수는 17번 입니다.

✅ 효과: 메모이제이션 적용으로 함수 호출 횟수가 1/3로 감소.

---

✅ 이해도 체크리스트

1. 재귀함수에 대한 설명과 장단점은?
   • 정답: 재귀함수는 함수가 자기 자신을 다시 호출하는 함수.
   • 장점: 코드가 간결하고, 문제를 단순하게 나눠서 해결 가능.
   • 단점: 스택 오버플로우, 메모리 사용 증가, 속도 저하.
2. 재귀함수 사용 시 발생할 수 있는 단점과 해결 방법은?
   • 정답:
     • 단점: 스택 오버플로우, 메모리 사용 증가, 성능 저하.
     • 해결 방법:
       • 꼬리 재귀 최적화
       • 메모이제이션
       • 동적 계획법(DP)
3. 메모이제이션이란?
   • 정답: 중복된 계산을 방지하기 위해 이미 계산한 값을 저장해두는 기법.
   • 원리:
     • 이미 계산된 값을 메모리에 저장.
     • 동일한 계산이 필요할 때 저장된 값을 재사용.

---

이 정리된 내용을 통해 재귀함수와 메모이제이션의 개념을 확실히 다지고, 실무에서도 활용해 보세요! 🚀

 

📌 Python 함수 심화 – oz_fibo 메모이제이션 프로세스

---

✅ 코드 구조 설명

memo = {
    1: 1,
    2: 1,
}

count = 0

def oz_fibo(n):
    print(f'피보나치 수열 {n}을 구하는 중입니다.')
    global count
    count += 1

    if n in memo:
        return memo[n]
    else:
        output = oz_fibo(n-1) + oz_fibo(n-2)
        memo[n] = output
        return output

n = int(input("구하고자하는 피보나치의 수열의 수를 입력해주세요"))
oz_fibo(n)
print(f'피보나치 수열 {n}을 구하기 위해 계산된 횟수는 {count}입니다')

---

✅ 프로세스 단계별 설명

1. memo
   • 피보나치 수열의 값을 저장하는 딕셔너리.
   • 처음에 1과 2번째 값은 기본값 1로 저장되어 있음.
2. count
   • 함수 호출 횟수를 세기 위해 사용되는 변수.
3. oz_fibo(n) 함수
   • 함수가 호출되면 현재 계산 중인 피보나치 수열의 숫자를 출력.
   • if n in memo → 이미 계산된 값은 바로 반환.
   • else → 재귀적으로 n-1과 n-2를 호출하여 값을 계산하고, memo에 저장 후 반환.
4. 최종 출력
   • 사용자가 입력한 n에 대해 피보나치 수열 값을 계산.
   • 전체 함수 호출 횟수(count)를 출력.

---

✅ 예시: n = 5일 때의 과정

oz_fibo(5) → oz_fibo(4) + oz_fibo(3)
oz_fibo(4) → oz_fibo(3) + oz_fibo(2)
oz_fibo(3) → oz_fibo(2) + oz_fibo(1)
oz_fibo(2) → 1 (memo에서 반환)
oz_fibo(1) → 1 (memo에서 반환)

oz_fibo(3) → 1 + 1 = 2
oz_fibo(2) → 1 (memo에서 반환)

oz_fibo(4) → 2 + 1 = 3
oz_fibo(3) → 2 (memo에서 반환)

oz_fibo(5) → 3 + 2 = 5

최종 출력 결과

피보나치 수열 5을 구하는 중입니다.
피보나치 수열 4을 구하는 중입니다.
피보나치 수열 3을 구하는 중입니다.
피보나치 수열 2을 구하는 중입니다.
피보나치 수열 1을 구하는 중입니다.
피보나치 수열 3을 구하는 중입니다.
피보나치 수열 2을 구하는 중입니다.
피보나치 수열 5을 구하기 위해 계산된 횟수는 7입니다

---

✅ 왜 메모이제이션을 사용할까?

• 중복 계산을 피하여 효율성을 극대화합니다.
• 같은 값을 반복해서 계산하지 않고, 이미 계산된 값을 memo에서 바로 가져오기 때문에 계산 속도가 빨라집니다.
• 특히 피보나치 수열과 같은 재귀적 문제에서 성능 향상에 필수적입니다.

---

✅ 메모이제이션 없이 작성할 경우

def oz_fibo(n):
    if n == 1 or n == 2:
        return 1
    return oz_fibo(n-1) + oz_fibo(n-2)

print(oz_fibo(5))

• 동일한 값이 중복으로 계산되기 때문에, n 값이 커질수록 성능 저하가 발생합니다.
• 호출 횟수도 기하급수적으로 증가하게 됩니다.

---

✅ 메모이제이션의 장점 정리

1. ✅ 중복 계산을 피함 → 빠른 계산 속도
2. ✅ 재귀 호출 최소화 → 메모리 효율성 증가
3. ✅ 실행 시간 단축 → 최적화된 성능

---

🚀 결론: 메모이제이션은 재귀적 문제에서 반드시 활용해야 하는 기법입니다. memo를 통해 중복된 계산을 제거하고, 효율적으로 값을 반환하는 방법을 익히면 코딩 실력이 한층 더 향상될 거예요! 😊

📌 Python 함수 심화 – 재귀함수와 메모이제이션

---

✅ 1. 재귀함수란?

• **재귀함수(Recursive Function)**는 함수 내에서 자기 자신을 호출하는 함수입니다.
• 복잡한 문제를 작고 단순한 동일 문제로 나누어 해결할 때 사용합니다.
• 대표적인 예: 팩토리얼, 피보나치 수열, 트리 탐색 등

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

print(factorial(5))  # 출력: 120

---

✅ 2. 재귀함수의 장점과 단점

🎯 장점

1. ✅ 코드가 간결하다.
   • 복잡한 문제를 단순하고 깔끔하게 표현할 수 있음.
2. ✅ 문제 해결이 직관적이다.
   • 수학적 문제나 트리, 그래프와 같은 구조적 문제를 표현하기 용이함.
3. ✅ 분할 정복 알고리즘에 유용하게 사용됨.

⚠️ 단점

1. ❌ 스택 오버플로우 위험
   • 너무 많은 재귀 호출로 인해 RecursionError 발생 가능.
2. ❌ 성능 저하
   • 같은 값을 중복으로 반복 계산하여 불필요한 연산이 많아짐.
3. ❌ 메모리 사용량 증가
   • 함수 호출 스택이 계속 쌓이기 때문에 메모리 낭비가 발생할 수 있음.

---

✅ 3. 재귀함수 사용 시 발생할 수 있는 단점과 해결 방법

문제점 해결 방법

스택 오버플로우

1. 재귀 깊이 제한 설정

                2. **꼬리 재귀 최적화** (Python에서는 기본적으로 미지원) |

| 성능 저하 | 1. 메모이제이션 사용 2. 반복문으로 전환 | | 메모리 낭비 | 1. 메모이제이션으로 중복 계산 제거 2. 동적 계획법(DP) 적용 |

---

✅ 4. 메모이제이션이란?

• **메모이제이션(Memoization)**은 이미 계산한 결과를 저장하여, 동일한 계산을 반복하지 않도록 하는 기법입니다.
• 재귀 함수의 성능 저하를 방지하기 위해 사용됩니다.
• **동적 계획법(Dynamic Programming)**의 핵심 기법 중 하나입니다.

---

✅ 5. 메모이제이션 적용 예시 (피보나치 수열)

❌ 메모이제이션을 사용하지 않은 재귀 함수

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(5))  # 출력: 5

• 동일한 값을 중복 계산하여 비효율적임.
• fibonacci(3) 같은 값이 여러 번 중복 계산됩니다.

✅ 메모이제이션 적용한 재귀 함수

memo = {1: 1, 2: 1}

def fibonacci(n):
    if n in memo:
        return memo[n]
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return memo[n]

print(fibonacci(5))  # 출력: 5

• 이미 계산된 값은 memo에서 바로 반환하므로, 중복 계산을 제거하여 성능이 향상됩니다.

---

✅ 6. 메모이제이션의 장점

1. ✅ 중복된 계산을 방지하여 실행 시간을 대폭 단축시킵니다.
2. ✅ 재귀 호출을 최소화하여 성능을 향상시킵니다.
3. ✅ 메모리 낭비를 줄이고 효율성을 높일 수 있습니다.

---

✅ 결론

• 재귀함수는 복잡한 문제를 간결하고 직관적으로 표현할 수 있지만, 성능과 메모리 문제가 발생할 수 있습니다.
• 이를 해결하기 위해 메모이제이션을 적극 활용하면, 재귀 함수의 단점을 극복하고 효율적인 코드를 작성할 수 있습니다! 🚀