재귀(recursive)

• 파이썬 초정독 스터디 - 코딩테스트 합격자되기 파이썬 편 도서를 참고하여 작성된 글입니다.

재귀 함수

• 자기 자신을 호출(recursive call)하는 방법
• 문제를 반복적이고, 작은 단위로 분해햐여 처리
• 더이상 분해할 수 없는 base condition에 도달하면 호출을 종료

재귀 함수를 사용하는 이유

• 같은 논리를 작은 단위로 반복하여 해결 가능한 경우, 복잡한 문제를 단순화 하여 해결할 수 있음
• 특히 트리 구조의 논리를 처리하고자 할 때 유용함
• 코드를 간결하게 작성할 수 있음

재귀 함수 사용시 주의할 점

• 모든 함수는 호출시 메모리를 차지하며, 컴퓨터의 메모리는 한정적이므로 recursion depth 또한 제한적임
  • 따라서 반드시 base condition이 필요함
• 함수 호출 스택
  • 재귀 함수는 호출될 때마다 함수의 매개변수, 지역 변수, 반환 주소 등을 저장하기 위해 스택에 새로운 프레임이 추가함
  • 재귀 호출이 많아질수록 스택에 쌓이는 프레임의 수도 많아져, 메모리 사용량이 증가
• 따라서 스택 오버플로우나, 메모리 사용으로 인한 성능 문제를 야기할 수 있음
• 재귀 함수를 사용할 때는 문제의 크기가 점점 줄어들어야 함. 일정한 반복이 지속된다면 재귀가 끝나지 않기 때문.

재귀 함수를 반복문으로 변환하기

재귀 함수로 작성된 팩토리얼

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

반복문으로 작성한 팩토리얼

def factorial(n):
    result = 1
    for i in range(n, 1, -1):
        result *= i
    return result