재귀 이해하기

Python으로 배우는 자료구조와 알고리즘

Miriam Antona

Software engineer

정의

  • 함수가 자기 자신을 호출
  • 대다수 반복문 상황
    • 반복문을 재귀로 대체 가능
  • 처음엔 복잡해 보이는 문제도 해결
Python으로 배우는 자료구조와 알고리즘

예시 - 팩토리얼

$n!$

Python으로 배우는 자료구조와 알고리즘

예시 - 팩토리얼

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

120
Python으로 배우는 자료구조와 알고리즘

예시 - 재귀로 구현한 팩토리얼

$n!= n$ · $(n-1)!$

def factorial_recursion(n):
  return n * factorial_recursion(n-1)
  • 무한 실행!
Python으로 배우는 자료구조와 알고리즘

예시 - 기본 사례 식별

  • 조건 추가
    • 알고리즘이 무한 실행되지 않도록 함
  • 팩토리얼 기본 사례 -> $n=1$
def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120
Python으로 배우는 자료구조와 알고리즘

재귀의 동작 원리

  • 컴퓨터는 함수 추적에 스택 사용
    • 호출 스택
Python으로 배우는 자료구조와 알고리즘

재귀의 동작 원리

  • factorial(5) 시작
  • factorial(5)가 끝나기 전에 -> factorial(4) 시작
  • factorial(4)가 끝나기 전에 -> factorial(3) 시작

함수 하나를 나타내는 요소가 있는 큐 그림.

Python으로 배우는 자료구조와 알고리즘

재귀의 동작 원리

  • factorial(5) 시작
  • factorial(5)가 끝나기 전에 -> factorial(4) 시작
  • factorial(4)가 끝나기 전에 -> factorial(3) 시작
  • factorial(3)가 끝나기 전에 -> factorial(2) 시작

두 함수 요소가 있는 큐 그림.

Python으로 배우는 자료구조와 알고리즘

재귀의 동작 원리

  • factorial(5) 시작
  • factorial(5)가 끝나기 전에 -> factorial(4) 시작
  • factorial(4)가 끝나기 전에 -> factorial(3) 시작
  • factorial(3)가 끝나기 전에 -> factorial(2) 시작
  • factorial(2)가 끝나기 전에 -> factorial(1) 시작

세 함수 요소가 있는 큐 그림.

Python으로 배우는 자료구조와 알고리즘

재귀의 동작 원리

  • factorial(5) 시작
  • factorial(5)가 끝나기 전에 -> factorial(4) 시작
  • factorial(4)가 끝나기 전에 -> factorial(3) 시작
  • factorial(3)가 끝나기 전에 -> factorial(2) 시작
  • factorial(2)가 끝나기 전에 -> factorial(1) 시작

네 함수 요소가 있는 큐 그림.

Python으로 배우는 자료구조와 알고리즘

재귀의 동작 원리

  • factorial(1) 종료
    • 1 반환
  • factorial(2) 종료

네 함수 요소가 있는 큐 그림.

Python으로 배우는 자료구조와 알고리즘

재귀의 동작 원리

  • factorial(1) 종료
    • 1 반환
  • factorial(2) 종료
    • 2 반환

마지막 함수에 반환값이 표시된, 네 함수 요소가 있는 큐 그림.

Python으로 배우는 자료구조와 알고리즘

재귀의 동작 원리

  • factorial(1) 종료
    • 1 반환
  • factorial(2) 종료
    • 2 반환
  • factorial(3) 종료
    • 6 반환

세 함수 요소가 있는 큐 그림.

Python으로 배우는 자료구조와 알고리즘

재귀의 동작 원리

  • factorial(1) 종료
    • 1 반환
  • factorial(2) 종료
    • 2 반환
  • factorial(3) 종료
    • 6 반환
  • factorial(4) 종료
    • 24 반환

두 함수 요소가 있는 큐 그림.

Python으로 배우는 자료구조와 알고리즘

재귀의 동작 원리

  • factorial(1) 종료
    • 1 반환
  • factorial(2) 종료
    • 2 반환
  • factorial(3) 종료
    • 6 반환
  • factorial(4) 종료
    • 24 반환
  • factorial(5) 종료
    • 120 반환

하나의 함수 요소가 있는 큐 그림.

Python으로 배우는 자료구조와 알고리즘

재귀의 동작 원리

  • factorial(1) 종료
    • 1 반환
  • factorial(2) 종료
    • 2 반환
  • factorial(3) 종료
    • 6 반환
  • factorial(4) 종료
    • 24 반환
  • factorial(5) 종료
    • 120 반환

빈 큐 그림.

Python으로 배우는 자료구조와 알고리즘

동적 계획법

  • 최적화 기법
  • 주로 재귀에 적용
  • 재귀 알고리즘의 복잡도 감소
  • 사용 사례:
    • 더 작은 하위 문제로 분할 가능
    • 하위 문제가 겹침
  • 하위 문제 해를 저장해 재계산 방지
    • 메모이제이션
Python으로 배우는 자료구조와 알고리즘

연습해 봅시다!

Python으로 배우는 자료구조와 알고리즘

Preparing Video For Download...