재귀란?

Python으로 코딩 인터뷰 문제 연습하기

Kirill Smirnov

Data Science Consultant, Altran

정의

재귀는 문제를 자기 자신으로 정의하는 과정입니다
재귀는 함수가 자신을 하위 루틴으로 호출하는 과정입니다

예시: 팩토리얼 $n!$

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1$

$n = 4$:

$4! = 4\cdot3\cdot2\cdot1$

4! = 24

팩토리얼 - 반복 접근법

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1 = $

$ = 1\cdot2\cdot3\cdot...\cdot n$

반복적 해법:

# iterative factorial
def fact_iter(n):
    result = 1
    # looping over numbers from 1 to n
    for num in range(1, n+1)
        result = num * result

    return result

$n = 4:$

result = 1

result = 1 * result(1) = 1
result = 2 * result(1) = 2
result = 3 * result(2) = 6
result = 4 * result(4) = 24

$4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24$

팩토리얼 - 재귀 접근법

$n!$ $=n\cdot(n-1)!$

def fact_rec(n):
    return n * fact_rec(n-1)

이 코드의 문제는 무엇일까요?

fact_rec(4)

RecursionError

기준 사례를 정의해야 합니다!

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1$

정지 조건/기준 사례: $1! = 1$

def fact_rec(n):
    if n == 1:
        return 1
    return n * fact_rec(n-1)

fact_rec(4)

마무리

재귀 함수는 두 가지 핵심 구성요소가 있습니다:

자기 자신의 더 작은 문제로의 재귀 호출
무한 호출을 막는 기준 사례(base case)

예시 - 의사결정나무

의사결정나무

의사결정나무로 분류하기

의사결정나무 순회

x - 새로운 샘플 $(x_1, x_2)$

# 범주를 찾는 의사코드:

category = pred(node, x):

  # 분할이 있는지 확인
  if node.hasSplitting:

    # 어느 자식 노드로 갈지 확인
    if node.goToLeftChild(x):
      return pred(node.leftChild, x)   
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

의사결정나무 순회

의사결정나무로 예측하기

x - 새로운 샘플 $(x_1, x_2)$

# 범주를 찾는 의사코드:

category = pred(node, x):

  # 분할이 있는지 확인
  if node.hasSplitting:

    # 어느 자식 노드로 갈지 확인
    if node.goToLeftChild(x):
      return pred(node.leftChild, x) 
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

  # 범주 반환
  return node.category

연습해 봅시다!

Python으로 코딩 인터뷰 문제 연습하기