재귀 함수

📌 재귀 함수(Recursive Function)

재귀 함수란 자기 자신을 호출하는 함수이다.

재귀적으로 문제를 푼다는 것은 같은 형태의 더 작은 문제를 풀어야 한다.
또 다른 말로 부분 문제(Subproblem)이라고도 한다.

💻 예시

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

📝 재귀 함수의 단점

위치를 기록해두는 곳을 Call Stack이라고 하는데, 이 Call Stack이 너무 많이 쌓이게 되면 더 이상 기록할 공간이 없어지고 StackOverflowError가 발생한다.

---

📌 재귀 함수 연습

✅ 피보나치 수열

파라미터로 11 이상의 자연수 n을 받고, n번째 피보나치 수를 리턴하는 재귀 함수 fib를 쓰세요. 반복문은 쓰면 안됩니다!

def fib(n):
    if n <= 1:
        return n
    return fib(n-2) + fib(n-1)

for i in range(1, 11):
    print(fib(i))

---

✅ 숫자 합

n번째 삼각수(triangle number)는 자연수 11부터 n까지의 합입니다. 파라미터로 정수값 n을 받고 n번째 삼각수를 리턴해주는 재귀 함수 triangle_number를 쓰세요. n은 11 이상의 자연수라고 가정합시다.

def triangle_number(n):
    if n <= 1:
        return n
    return triangle_number(n-1) + n

for i in range(1, 11):
    print(triangle_number(i))

---

✅ 자릿수 합

파라미터로 정수값 n을 받고 n의 각 자릿수의 합을 리턴해주는 재귀함수 sum_digits를 쓰세요.

def sum_digits(n):
    if (n // 10) == 0:
        return n
    return sum_digits(n // 10) + (n % 10)

# 테스트
print(sum_digits(22541))
print(sum_digits(92130))
print(sum_digits(12634))
print(sum_digits(704))
print(sum_digits(3755))

---

✅ 리스트 뒤집기

파라미터로 리스트 some_list를 받고, 뒤집힌 리스트를 리턴해 주는 재귀 함수 flip을 쓰세요.

def flip(some_list):
    if len(some_list) == 0 or len(some_list) == 1:
        return some_list
    return some_list[-1:] + flip(some_list[:-1]):
        return some_list
    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)

---

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

def binary_search(element, some_list, start_index=0, end_index=None):
    
    if end_index == None:
        end_index = len(some_list) - 1

    if start_index > end_index:
        return None

    med = (start_index + end_index) // 2

    if some_list[med] == element:
        return some_list.index(element)
    elif some_list[med] < element:
        return binary_search(element, some_list, med+1, end_index)
    else:
        return binary_search(element, some_list, start_index, med-1)
        
# 테스트
print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

---

✅ 하노이의 탑

이 게임의 목표는 왼쪽 기둥에 있는 원판들을 모두 오른쪽 기둥으로 옮기는 것이다.

• 한 번에 하나의 원판만 옮길 수 있다.
• 큰 원판이 작은 원판 위에 있어서는 안 된다.

하노이의 탑 게임의 해답을 출력해주는 함수 hanoi를 사용해라.
hanoi는 파라미터로 원판 수 num_disks, 게임을 시작하는 기둥 번호 start_peg, 그리고 목표로 하는 기둥 번호 nd_peg를 받고, 재귀적으로 문제를 풀어 원판을 옮기는 순서를 모두 출력한다.

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):
    if num_disks == 1:
        return move_disk(num_disks, start_peg, end_peg)

    med_peg = 6 - (start_peg + end_peg)

    hanoi(num_disks - 1, start_peg, med_peg)
    move_disk(num_disks, start_peg, end_peg)
    hanoi(num_disks - 1, med_peg, end_peg)

hanoi(3, 1, 3)