재귀 함수(Recursive Function)

자기 자신을 호출하는 함수

 

Recursive case: 현 문제가 너무 커서, 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우
Base case: 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우

def count(n):
	if n > 0:
    	print(n)
        count(n - 1)
        
count(4)

재귀적으로 문제를 풀때는 따로 풀어야 하는 부분 문제를 고려해서 작성

n! (n 팩토리얼) 구하기

n = 0 일때 -> n! = 1(base case)

n > 0 일때 -> n! = (n-1)! * n

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

print(factorial(4))

 

종류

1. 피보나치 수열

-> 첫 번째 항과 두 번째 항이 1이고, 세 번째 항부터는 바로 앞의 두 항의 합으로 정의된 수열

# n번째 피보나치 수를 리턴
# 재귀함수 사용
def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)
        
for i in range(1, 11):
    print(fib(i))

2. n번째 삼각수

-> n 번째 삼각수(triangle number)는 자연수 1부터 n까지의 합

# 1부터 n까지의 합을 리턴
def triangle_number(n):
    if n == 1:
        return 1
    else:
        return n + triangle_number(n - 1)

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

3. 자릿수 합

-> n을 파라미터로 받아 n의 각 자릿수의 합을 리턴

# n의 각 자릿수의 합을 리턴
# 22541 => 14
# 92130 => 15
def sum_digits(n):
    
    if n < 10:
        return n
    else:
        return sum_digits(n // 10) +  sum_digits(n % 10)

4. 리스트 뒤집기

-> 파라미터로 리스트를 받아 뒤집힌 리스트를 리턴

# 파라미터 some_list를 거꾸로 뒤집는 함수
def flip(some_list):
    if len(some_list) == 1:
        return some_list
    else:
        return some_list[-1:] + flip(some_list[:-1])
# 끝에서 부터 첫번째 까지 슬라이싱
print(aa[-1:]) # [3]
# 끝에서 첫번째 전까지 슬라이싱
print(aa[:-1]) # [1,2]

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

5. 하노이의 탑

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)

    mid_peg = (6 - start_peg - end_peg)
    
    # 1. 가장 큰 원판을 제외하고 나머지 원판들을 start_peg에서 mid_peg로 이동
    hanoi(num_disks -1, start_peg, mid_peg)
    
    # 2. 가장 큰 원판을 start_peg에서 end_peg로 이동
    move_disk(num_disks, start_peg, end_peg)
    
    # 3. 나머지 원판들을 mid_peg에서 end_peg로 이동
    hanoi(num_disks -1, mid_peg, end_peg)

hanoi(3, 1, 3)