재귀함수

재귀함수

실행 도중에 스스로를 재호출하는 함수

• 기저 사례(base case)
  재귀함수가 더 이상 호출되지 않도록 하는 특정 조건 (=재귀 함수 탈출 조건)

  def factorial(n): # 재귀함수
     if n <= 0: return 1 # 기저 사례
     return n * factorial(n - 1)

  -> 기저사례를 설정하지 않으면 RecursionError 발생한다.
  

❓스택 프레임

함수가 호출되면 메모리에 생기는 공간. 함수 실행에 필요한 지역 변수들이 할당됨.
return을 만나면 함수가 종료되는데, 만들어진 함수의 스택 프레임 역시 소멸됨.
-> 스택 프레임은 함수 호출 시 생성, 함수 종료 시 소멸

Recursion Depth Error

• 메모리에 생성되는 스택 프레임은 생성될 수 있는 크기에 한계가 있다. 계속 쌓이다가 최대 한계치에 도달하는 경우 Recursion Depth 에러가 발생한다.
• 함수가 어떤 함수를 계속해서 호출하다 스택 프레임으로 쓰일 메모리 공간이 모자라지는 상황을 스택 오버플로(stack overflow)라고 한다.

---

구현해보기

S = {1, 2, 3}일 때 집합 S의 모든 순열 구하기

sol)
문제를 여러개의 부분문제로 쪼개서 답 구하기

함수를 permutation({1, 2, 3})이라고 하면
1을 출력 후 permutation({2, 3}), 2를 출력 후 permutation({1, 3}), 3을 출력 후 permutation({1, 2})
위와 같은 그림을 재귀 트리라고 칭한다.

def permutation(arr, start):
    if len(arr) == start: # start가 배열의 길이와 같아지면 종료
        print(arr)
        return
    
    for i in range(start, len(arr)): # 첫번째(맨앞) 자리 설정
        arr[start], arr[i] = arr[i], arr[start]
        permutation(arr, start + 1) # 재귀. start 1 증가
        arr[start], arr[i] = arr[i], arr[start]

data = [1, 2, 3]
permutation(data, 0)