중급반 1주차에는 완전탐색과 재귀에 대해 공부할 예정입니다.

2개를 묶어놓은 이유는 완전탐색은 재귀로 푸는 경우가 많아서 재귀를 잘 공부해 놓는다면 완전탐색을 수월하게 공부할 수 있습니다. 그렇다면 우선 재귀에 대해서 알아보겠습니다.

01 재귀

재귀는 하나의 함수에서 자기 자신을 호출해 작업을 수행하는 알고리즘입니다.

재귀의 가장 큰 특징은 이렇습니다.

<aside> 1️⃣ 재귀가 종료되는 조건과 자기 자신을 호출하는 파트로 나뉘어져 있다.

</aside>

<aside> 2️⃣ 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다.(base condition)

</aside>

<aside> 3️⃣ 모든 입력은 base condition으로 수렴한다.

</aside>

가장 쉬운 예로 1부터 5까지 곱하는 팩토리얼 함수를 만들어보겠습니다.

def factorial(n):
  if n == 0:
    return 1
  else:
    return n * factorial(n-1)

위 함수에서 if n== 0 return 1이 base condition 즉 종료조건입니다.

그 아래 부분이 자기 자신을 호출하는 부분이고 n이 1씩 줄어들면서 base condition인 n == 0으로 수렴하고 있죠. 모든 재귀가 이 형식을 따릅니다.

재귀는 또 다음과 같은 특징을 가지고 있습니다.

• 모든 재귀 함수는 재귀 구조 없이 반복문만으로 동일한 동작을 하는 함수를 만들 수 있습니다.
• 재귀는 적재적소에 사용하면 코드가 간결해지지만 함수 호출이 꽤 비용이 큰 연산이기 때문에 메모리와 시간에서는 손해를 봅니다. 그렇기 때문에 굳이 재귀를 쓰지 않아도 구현에 큰 어려움이 없으면 재귀 대신 반복문으로 코드를 짜는것도 좋습니다.