T.I.L Apr 27, 2023 (재귀함수의 이해)

재귀함수

---

1. 재귀함수: 스스로를 호출하는 함수

 

2. Django 개발할 때에는 크게 사용할 필요는 없으나 코딩 테스트를 위해서는 모르면 안되는 함수

 

3. 반복문으로도 구현이 가능하지만 재귀함수가 더 효율적입니다.

 

4-1. 리턴값을 활용하지 않는 재귀함수

def recursion(n):
    if n < 5:
        print(n)
        recursion(n + 1)
        
recursion(1)

 

4-2. 리턴값을 활용하는 재귀함수

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

print(recursion(4))

 

5. 재귀함수는 종료조건을 고려하는것이 중요

3-1, 3-2 재귀함수 예시 코드들이 값을 출력하고 멈출 수 있었던 이유는 코드가 종료될 수 있는 조건이

있었기 때문입니다.

 

반대로 아래와 같이 종료 조건이 없는 코드가 있다면 어떻게 될까요?

def recursion(n):
    print(n)
    recursion(n+1)
    
recursion(1)

 

결과는 아래와 같이 에러가 발생합니다.

RecursionError: maximum recursion depth exceeded while calling a Python object

 

6. 최대 재귀 깊이(maximum recursion depth): 재귀함수를 최대로 호출할 수 있는 횟수 파악

import sys

print(sys.getrecursionlimit())

# 1000

위의 코드로 재귀함수를 최대로 호출할 수 있는 횟수를 파악할 수 있습니다.

 

7. 재귀문제 유형 파악하기

재귀로 코드를 짤 수 있다는 것을 어떻게 파악할 수 있을까요?

*문제 풀이 과정의 일부분이 문제를 푸는 전체 과정과 유사하다면 재귀로 코드를 짤 수 있다는 것을 파악할 수 있습니다.