재귀 함수 연습하기

지난 시간에 재귀 함수의 개념을 함께 알아보았습니다. 이번 시간에는 배운 개념을 활용하여 여러 가지 재귀 함수 문제를 풀어봅시다. 문제의 해석을 보기 앞서 직접 문제를 풀어보시길 바랍니다. 혼자서 생각하는 시간은 매우 중요합니다. 어렵더라도 꼭 한 번 생각해본 뒤 해설을 보세요.

🪐 피보나치 수열

학창 시절 수학 시간에 배웠던 피보나치 수열을 기억하시나요? 피보나치 수열은 바로 앞의 두 항의 합으로 정의된 수열입니다. 첫 번째 항과 두 번째 항은 1이지만 세 번째 항부터는 두 항의 합을 구해야 합니다.

예를 들어, 세 번째 항은 첫 번째 항 1과 두 번째 항 1을 더한 2가 되고 네 번째 항은 두 번째 항 1과 세 번째 항 2를 더한 3이 됩니다.

이제 재귀 함수 fib을 작성해봅시다. 이 함수는 파라미터로 1 이상의 자연수 n을 받고, n 번째 피보나치 수를 리턴합니다.

주의해야 할 것은 반드시 재귀 함수로 써야 한다는 점입니다. 반복문으로도 구현이 가능하지만 개념을 익히기 위해 오로지 재귀 함수만을 활용해야 합니다.

지난 시간에 우리는 재귀 함수의 개념을 배우며 base case와 recursive case를 정의하는 것이 정말 중요하다는 것을 알았습니다. 따라서, 재귀 함수를 구현하기 전 base case와 recursive case부터 정의해봅시다.

우선, base case는 문제가 충분히 작아서 더 작은 부분 문제로 나누지 않고도 바로 답을 구할 수 있는 경우를 말합니다. 그럼 피보나치 수열의 base case는 무엇일까요?

피보나치 수열의 정의를 다시 한 번 봅시다. 첫 번째 항과 두 번째 항은 늘 1입니다. 이는 이미 정의 된 내용이라 생각할 필요 없이 바로 답을 구할 수 있는 경우이죠? 따라서 이 조건을 피보나치 수열의 base case로 볼 수 있습니다. 이를 코드로 구현해 보면 다음과 같습니다.

if n < 3:
    return 1

다음으로 recursive case를 생각해봅시다. 현재 문제가 너무 커서 같은 형태의 더 작은 부분 문제로 나눌 수 있는 경우를 recursive case라 합니다. fib(4)를 예로 들어볼까요? 정의에 따르면 피보나치의 네 번째 항은 두 번째 항과 세 번째 항의 합입니다.

따라서, fib(4)는 'fib(3)+fib(2)'와 같습니다. fib(3)과 fib(2)는 같은 형태의 더 작은 부분인 부분 문제가 되구요.

이제 이를 일반화하기만 하면 됩니다. 4가 n이라고 하면 fib(4)는 fib(n), fib(3)과 fib(2)는 각각 fib(n-1), fib(n-2)로 나타낼 수 있습니다. 코드로 구현하면 다음과 같습니다.

return fib(n-1) + (n-2)

이제 전체 코드와 문제 풀이 예시를 봅시다.

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

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

1
1
2
3

❗ 시간 복잡도

fib 함수를 구성하는 base case와 두 개의 재귀적 호출 모두 인풋 크기와는 상관이 없으므로 fib 호출 한 번의 시간 복잡도는 O(1)입니다.

다음으로 fib 함수가 재귀적으로 실행될 때의 경우를 봅시다. 매 호출마다 fib 함수가 재귀적으로 두 번 더 호출됩니다. 그리고 호출된 두 함수는 각각 또 다시 두 번씩 재귀적으로 함수를 호출합니다. 그럼 총 네 번의 호출이 이뤄지겠죠?

이처럼 인풋 n이 3보다 작아지는 base case까지는 반복적으로 두 개의 새로운 재귀 호출이 발생합니다. 각 단계마다 원래 문제의 두 배로 문제가 늘어나는 것입니다. 따라서, 이 단계의 개수는 n과 비례하고 문제는 약 n번 두 배씩 커집니다. 이를 시간 복잡도로 표현하면 O(2^n)이 됩니다.

🪐 n번째 삼각수

저번 시간에 우리는 자연수 1부터 자연수 n까지의 곱을 구하는 팩토리얼을 배웠습니다. 이번에는 곱이 아닌 합의 경우를 봅시다. n번째 삼각수(triangle number)는 자연수 1부터 n까지의 합입니다.

triangle_number는 파라미터로 정수값 n을 받고 n번째 삼각수를 리턴해주는 재귀함수입니다. 이때, n은 1 이상의 자연수라 가정합니다. 마찬가지로 반복문 없이 오직 재귀를 이용하여 함수를 작성해야 합니다.

우선, base case와 recursive case부터 구해봅시다. 이 함수에서 부분 문제로 더 나눌 수 없는 base case는 어떤 걸까요? 바로 n이 1이 되는 순간입니다. n이 1이면 별다른 연산 없이 곧바로 1을 출력해야 하기 때문이죠.

if n == 1:
    return 1

다음으로, recursive case도 구해봅시다. 삼각수 연산에서 문제가 너무 커서 부분 문제로 나누어지는 recursive case는 어떤 것일까요? triangle_number(4)의 사례를 봅시다.

정의에 따르면 triangle_number(4)의 값은 1부터 4까지를 더한 수입니다. 그렇다면 triangle_number(3)은 어떤가요? 1부터 3까지죠? 따라서, triangle_number 연산을 일반화하면 'triangle(n) = triangle(n-1) + n'이 됩니다.

return triangle(n-1) + n

이제 전체 코드와 문제 풀이 예시를 봅시다.

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

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

1
3
6
10
15

앞서 피보나치 사례와 마찬가지로 일반화된 연산이 재귀함수에 반영됩니다. 이를 알아두면 복잡하게 생각할 필요없이 재귀함수의 끝 조건과 일반화 된 식부터 떠올리면 되기 때문에 매우 유용합니다.

❗ 시간 복잡도

우선 재귀적인 호출을 제외하고 생각해 봅시다. base case의 시간 복잡도는 인풋의 크기와 관련이 없으므로 O(1)입니다. recursive case에서도 triangle_number(n-1)의 재귀적 호출을 제외한 나머지는 O(1)입니다.

마지막으로 재귀적으로 호출되는 부분은 총 n번 호출되기 때문에 총 O(n)의 시간이 소요된다고 할 수 있습니다.

🪐 자릿수 합

재귀 함수 sum_digit은 파라미터로 정수 n을 받고 n의 각 자릿수 합을 리턴해줍니다. 반복문 없이 재귀 함수를 활용해서 코드를 작성해 봅시다.

sum_digit의 base case는 무엇인가요? sum_digit을 특별한 연산 없이 바로 구하려면 n이 10보다 작은 수여야 됩니다. 왜냐하면 1의 자리의 경우 자릿수를 따로 구할 필요 없이 해당 수를 리턴하면 되니까요.

그렇다면 1의 자리를 수식으로 어떻게 표현할 수 있을까요? 가장 쉬운 방법으로는 n이 10보다 작다고 표현하면 됩니다.

if n < 10:
    return n

이제 recursive case도 구해봅시다. sum_digit(123)의 사례를 볼까요? 123은 10보다 큰 수로 sum_digit 연산을 하면 100의 자리수 1과 10의 자리수 2, 그리고 1의 자리수 3을 더한 6이 됩니다.

그보다 한 단계 아래인 sum_digit(12)를 봅시다. 12는 10보다 큰 수이고 10의 자리수 1과 1의 자리수 2를 더한 3이 됩니다. 마지막으로 sum_digit(1)은 1이 10보다 작으므로 1만을 추출합니다.

앞서 sum_digit(123)과 sum_digit(12) 사이에서 공통점을 찾으셨나요? sum_digit(123)은 sum_digit(12) 연산에서 마지막 자릿수인 3을 더한 것과 같습니다.

그렇다면 123이 12가 되기 위해서는 어떤 과정이 필요할까요? 100이 10이 되기 위해서는 어떤 연산이 필요한가요? 네, 맞습니다. 100을 10으로 나누면 되죠. 마찬가지로 123을 10으로 나누면 12.3이 됩니다.

그런데 뒤에 소수 부분은 필요가 없죠? Python에서 소수 부분을 제외한 나눗셈의 결괏값을 추출해주는 연산은 '버림 나눗셈(//)'을 활용하면 이 소수 부분을 버릴 수 있습니다.

그 다음, 1의 자리(마지막 자릿수)에 있는 수를 추출하기 위해 10을 나눈 연산의 나머지를 구하면 됩니다. Python에서는 '%'를 통해 나머지를 구할 수 있죠.

따라서, sum_digit을 일반화한 식은 이렇습니다.

return sum_digit(n//10) + n%10

이제 전체 코드와 문제 풀이 예시를 봅시다.

def sum_digit(n):
    if n < 10:
        return n
    return sum_digit(n//10) + n%10

print(sum_digit(32))
print(sum_digit(7))
print(sum_digit(594))

5
7
18

❗ 시간 복잡도

인풋 n의 자릿수 개수를 d라고 합시다. n이 123이면 d는 3이 됩니다.

sum_digit 함수의 base case 부분은 O(1)이 소요됩니다. 이는 n%10 연산도 마찬가지입니다. 그럼 이제 재귀적으로 호출되는 부분인 sum_digit만 보면 됩니다.

sum_digit이 재귀적으로 호출될 때마다 n은 매번 한 자리씩 줄어들기 때문에 약 1/10으로 줄어든다고 볼 수 있습니다. 따라서, sum_digit은 약 d번 호출되는 셈입니다. 그렇기 때문에 sum_digit의 시간 복잡도는 O(d)로 표현할 수 있죠.

만약 자릿수를 d로 표현하지 않고 바로 구한다면 자릿수를 나타내는 연산은 'log(10)n + 1'이므로 O(log(10)n)으로도 표현할 수 있습니다.

---

지금까지 재귀 함수의 간단한 사례를 보았습니다. 간단하지 않았다구요? 그렇다면 앞서 설명했던 대로 식을 일반화하는 연습을 해보세요. 일반화 식을 구하면 recursive case를 채우는 것이 좀 더 쉬워질 것입니다.

다음 시간에는 좀 더 어려운 재귀 함수 사례들을 함께 봅시다. 이번 챕터가 어렵지 않았다면 다음 챕터도 수월하게 이해할 수 있을 겁니다.

* 이 자료는 CODEIT의 '알고리즘의 정석' 강의를 기반으로 작성되었습니다.