19_Step : 이진탐색 & 재귀함수

이진탐색은 내가 찾고자 하는 데이터를 찾기 위해 쓰는 방법 중 하나인데 총 데이터의 절반을 잘라서 원하는 데이터가 있는지 보고 없으면 나머지 절반의 절반을 또 잘라 확인하는 식으로 찾는다.

만약 내가 7을 찾고 싶다면 1-2-3-4-5-6-7-8-9-10의 데이터 중 5에서 잘라 1-2-3-4-5를 확인해 보고 없으면 6-7-8-9-10의 데이터에서 찾게 되는데 이때 6-7-8-9-10을 또 나눠서 6-7-8에서 찾고 9-10에서 찾는다.

이런 식으로 절반씩 데이터를 쪼개가며 원하는 데이터가 포함되어 있는지 확인하며 찾아가기 때문에 O(logN)의 시간복잡도를 갖는다. 따라서 1~10까지 하나씩 찾아보는 O(N)의 시간 복잡도 보다 효율적이다.

 

그러나 규칙적으로 정렬되어 있는 데이터에서만 이진탐색이 가능하다.

 

재귀함수는 반복이라는 의미를 가지고 있는데 함수 안에서 자기 자신을 다시 불러서 함수가 또 실행되도록 만들어진 것이다. 그렇기 때문에 반드시 탈출하는 지점을 정해줘야한다. 안그러면 무한루프에 빠지기 때문에!!

 팩토리얼이 재귀함수의 단골손님인데

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

이렇게 간단하게 구현이 되는데 이렇게 코드를 짰을 경우 탈출하는 지점을 정해주지 않았다.

따라서,

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

print(factorial(60))

이와 같이 n이 1일때 탈출하라는 지점을 정해줘야 코드가 잘 돌아갈 것이다.