재귀 함수 : 자신을 호출하는 신기한 함수

재귀(recursion)함수란 호출된 함수가 자기 자신을 다시 호출하는 것

커다란 문제를 쪼개 부문 문제로 만들어 해결함으로써 전체 문제를 풀어 나가는 구조를 설계할 때 반드시 필요

• 再^{다시, 두번}
• 歸^{돌아오다, 돌아가다, 마치다}

재귀함수로 팩토리얼 구현하기

수학에서 어떤 수 n의 팩토리얼(factorial)은 1부터 n까지 곱을 의미, n! 이라고 표기 (0! 은 1)

\[4! = 1 \times 2 \times 3 \times 4\] \[4! = 3! \times 4\] \[n! = (n-1)! \times n\]

def factorial(n):
    if n <= 0: #1 재귀 함수가 더 이상 호출되지 않도록 하는 '특정 조건'
        return 1
    return factorial(n-1)*n


if __name__ == "__main__":
    factorial(6)

스택 프레임으로 재귀 함수 이해하기

• 스택 프레임
  • 함수 호출 시 메모리에 생기는 공간
  • 함수 실행에 필요한 지역 변수들이 할당됨
  • 함수를 호출 했을 때 생성, 함수 실행이 종료 되었을 때 소멸
• 상태 정보를 가지고 있는 지역 변수는 서로 다른 스택 프레임에 저장
• 함수 내에서 자기 자신을 호출해도 같은 기능의 코드를 실행, 실행 결과는 서로 다른 스택 프레임에 있는 지역 변수에 저장

재귀 트리

• 형태는 비슷하지만 크기가 다른 여러 작은 문제로 나눈 후 답을 구하고 그 답을 합침

재귀 함수 구현

1. 언제 어떤 매개 변수를 가지고 호출할지 정해야 함
2. 호출을 정지시켜 줄 기저 사례(base case)가 필요
3. 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성 가능
4. 모든 재귀 함수는 반복문으로 구현 가능
5. 재귀 함수가 반복문 보다 유리한 경우가 있고 불리한 경우가 있음
6. 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다
   • 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다