코드잇 알고리즘의 정석 :: 재귀함수

✏️ 본 포스팅은 코드잇 대학생 코딩캠프 1기 활동 기록 입니다. 

 

📌재귀함수

  ✽ 자신을 정의할 때 자기 자신을 재 참조하는 방법

  ✽ 재귀적으로 문제를 푼다 = 부분 문제의 답을 이용해서 기존 문제를 푼다

 

 

피보나치 수열

# n번째 피보나치 수를 리턴
def fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


# 테스트: fib(1)부터 fib(10)까지 출력
for i in range(1, 11):
    print(fib(i))

 

숫자 합

def triangle_number(n):
    # base case
    if n == 1:
        return 1
    else:
        return triangle_number(n - 1) + n


# 테스트: triangle_number(1)부터 triangle_number(10)까지 출력
for i in range(1, 11):
    print(triangle_number(i))

 

자릿수 합

# n의 각 자릿수의 합을 리턴
def sum_digits(n):
    if n < 10:
        return n
    elif n % 10 == 0:
        return 0 + sum_digits(int(n/10))
    else:
        temp = int((n - n % 10) / 10)
        return (n % 10) + sum_digits(temp)


# 테스트
print(sum_digits(22541))  # 14
print(sum_digits(92130))  # 15
print(sum_digits(12634))  # 16

 

리스트 뒤집기

# 파라미터 some_list를 거꾸로 뒤집는 함수
def flip(some_list):
    length = len(some_list)

    # base case
    if length <= 1:
        return some_list
    # recursive case
    else:
        return some_list[-1:] + flip(some_list[:-1])


# 테스트
some_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
some_list = flip(some_list)
print(some_list)

# 결과 [9, 8, 7, 6, 5, 4, 3, 2, 1]

 

이진 탐색 재귀로 구현해보기

def binary_search(element, some_list, start_index=0, end_index=None):
    # end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스
    if end_index == None:
        end_index = len(some_list) - 1

    mid = (start_index + end_index) // 2

    
    if start_index > end_index:
        return None
    else:
        if some_list[mid] > element:
            return binary_search(element, some_list, start_index, mid - 1)
        elif some_list[mid] < element:
            return binary_search(element, some_list, mid + 1, end_index)
        else:
            return mid


print(binary_search(2, [2, 3, 5, 7, 11]))  # 0
print(binary_search(0, [2, 3, 5, 7, 11]))  # None

 

하노이의 탑

 

def move_disk(disk_num, start_peg, end_peg):
    print("%d번 원판을 %d번 기둥에서 %d번 기둥으로 이동" % (disk_num, start_peg, end_peg))


def hanoi(num_disks, start_peg, end_peg):
    
    other_peg = 6 - start_peg - end_peg
	
    if num_disks == 0:  # base case
        return None
    else:
        if num_disks == 1:
            move_disk(num_disks, start_peg, end_peg)
        elif num_disks == 2:
            move_disk(num_disks - 1, start_peg, other_peg)
            move_disk(num_disks, start_peg, end_peg)
            move_disk(num_disks - 1, other_peg, end_peg)
        else:
            hanoi(num_disks - 1, start_peg, other_peg)
            move_disk(num_disks, start_peg, end_peg)
            hanoi(num_disks - 1, other_peg, end_peg)


# 테스트 코드 (포함하여 제출해주세요)
hanoi(3, 1, 3)

# 결과
# 1번 원판을 1번 기둥에서 3번 기둥으로 이동
# 2번 원판을 1번 기둥에서 2번 기둥으로 이동
# 1번 원판을 3번 기둥에서 2번 기둥으로 이동
# 3번 원판을 1번 기둥에서 3번 기둥으로 이동
# 1번 원판을 2번 기둥에서 1번 기둥으로 이동
# 2번 원판을 2번 기둥에서 3번 기둥으로 이동
# 1번 원판을 1번 기둥에서 3번 기둥으로 이동