코드잇의 알고리즘의 정석 수업을 수강하고 정리한 글입니다.
정확하지 않거나 빠트린 내용이 있을 수 있기 때문에 강의를 수강하시길 권장합니다.

재귀 함수의 두가지 요소

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

재귀 함수 연습을 할 때, 위 두가지 요소를 먼저 도출해보고 문제를 풀어보도록 하겠다.

피보나치 수열

문제

피보나치 수열이란 첫 번째 항과 두 번째 항이 1이고, 세 번째 항부터는 바로 앞의 두 항의 합으로 정의된 수열이다.

예를 들어서 세 번째 항은 첫 번째 항(1)과 두 번째 항(1)을 더한 2이며, 네 번째 항은 두 번째 항(1)과 세 번째 항(2)을 더한 3이 된다. 이러한 방식으로 피보나치 수열의 첫 10개 항은 1, 1, 2, 3, 5, 8, 13, 21, 34, 55이다.

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

# n번째 피보나치 수를 리턴
def fib(n):
    # 코드를 입력하세요.

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

# 콘솔 출력
1
1
2
3
5
8
13
21
34
55

풀이

$fib(1) = 1$
$fib(2) = 1$
$fib(3) = fib(1) + fib(2)$
$fib(4) = fib(2) + fib(3)$
$...$
$fib(n) = fib(n-2) + fib(n-1)$

따라서 다음과 같이 base case와 recursive case를 도출한다.
$n<=2\rightarrow fib(n)=1$
$n>2\rightarrow fib(n)=fib(n-2)+fib(n-1)$

코드

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

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

# 콘솔 출력
1
1
2
3
5
8
13
21
34
55

숫자 합

문제

$n$번째 삼각수(triangle number)는 자연수 1부터 $n$까지의 합이다. 파라미터로 정수값 n을 받고 $n$번째 삼각수를 리턴해주는 재귀 함수 triangle_number를 작성하라. $n$은 $1$ 이상의 자연수라고 가정한다. 반복문은 쓰면 안된다.

# 1부터 n까지의 합을 리턴
def triangle_number(n):
    # 코드를 입력하세요

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

# 콘솔 출력
1
3
6
10
15
21
28
36
45
55

풀이

$tn(1) = 1$
$tn(2) = 1 + 2 = tn(1) + 2 = 3$
$tn(3) = 1 + 2 + 3 = tn(2) + 3 = 6$
$tn(4) = 1 + 2 + 3 + 4 = tn(3) + 4 = 10$
$...$
$tn(n) = tn(n-1) + n$

따라서 다음과 같이 base case와 recursive case를 도출한다.
$n=1\rightarrow tn(n)=1$
$n>1\rightarrow tn(n)=tn(n-1)+n$

코드

# 1부터 n까지의 합을 리턴
def triangle_number(n):
    # base case
    if n == 1:
        return 1
    # recursive case
    return triangle_number(n-1) + n 
    
# 테스트: triangle_number(1)부터 triangle_number(10)까지 출력
for i in range(1, 11):
    print(triangle_number(i))

자릿수 합

문제

파라미터로 정수 값 n을 받고 n의 자릿수의 합을 리턴해주는 재귀함수 sum_digits를 작성하라. 반복문을 쓰면 안된다.

# n의 각 자릿수의 합을 리턴
def sum_digits(n):
    # 코드를 작성하세요.

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

# 콘솔 출력
14
15
16
11
20

풀이

$sd(22541) = sd(2254) + 1$
$sd(2254) = sd(225) + 4$
$sd(225) = sd(22) + 5$
$sd(22) = sd(2) + 2$
$sd(2) = 2$
...
$sd(n) = sd(n을 10으로 나눈 몫) + n을 10으로 나눈 나머지$

따라서 다음과 같이 base case와 recursive case를 도출한다.
$n < 10 \rightarrow sd(n) = n$
$n \geq 10 \rightarrow sd(n을 10으로 나눈 몫) + n을 10으로 나눈 나머지$

코드

# n의 각 자릿수의 합을 리턴
def sum_digits(n):
    # base case
    if n < 10:
        return n
    # recursive case
    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))

# 콘솔 출력
14
15
16
11
20