Python 재귀 함수 (Recursion)

재귀 함수 핵심 정리

함수와 조건문을 먼저 알고 오면 이해가 쉽습니다. 아래는 이 페이지에서 배울 내용을 미리 정리한 표입니다.

아래에서 하나씩 설명합니다.

재귀 함수란? 쌩기초

재귀 함수(Recursive Function)란 함수가 자기 자신을 다시 호출하는 함수입니다.

위 코드에서 f 함수 안에서 다시 f(n - 1)을 호출합니다. 이것이 재귀입니다.

재귀 함수의 두 가지 부분

재귀 함수는 항상 다음 두 부분으로 이루어집니다.

기저 조건이 없으면 어떻게 될까요?

함수 호출 체인 기초

재귀를 이해하기 전에, 먼저 함수가 다른 함수를 호출하는 구조를 알아보겠습니다. 함수에서 배운 것처럼, 함수는 다른 함수를 호출할 수 있습니다. 이렇게 함수들이 사슬처럼 이어지는 것을 호출 체인(chain)¹이라고 합니다.

이 코드는 재귀는 아니지만, 함수가 함수를 호출하는 체인 구조입니다. 만약 r100, r10, r1이 전부 같은 함수라면 어떨까요? 자기 자신을 계속 호출하는 재귀 함수가 됩니다.

호출 순서 추적하기

함수 호출 체인은 안쪽 함수부터 계산해야 합니다. 바깥 함수는 안쪽 함수의 반환값을 기다리기 때문입니다.

재귀 함수의 동작 원리 기초

함수 호출 체인에서 호출하는 함수가 자기 자신이면 재귀 함수입니다.

1부터 n까지의 합

def는 함수를 만드는 키워드, return은 결과값을 돌려주는 키워드입니다. 자세한 내용은 함수 페이지를 참고하세요.

재귀 호출 추적하기

total(5)를 호출하면 다음과 같이 동작합니다.

팩토리얼 예제

팩토리얼(Factorial)은 1부터 n까지의 모든 수를 곱한 값입니다. 5!(5 팩토리얼)은 수학에서 5부터 1까지 차례로 곱하라는 뜻으로, 느낌표(!)는 팩토리얼을 나타내는 수학 기호입니다. 5! = 5 x 4 x 3 x 2 x 1 = 120

"재귀 함수란?" 섹션의 첫 예제도 이 팩토리얼 함수입니다.

total(5)를 추적했던 것과 같은 방식으로 따라가 봅시다. 다른 점은 +가 *로 바뀐 것뿐입니다.

피보나치 예제

피보나치 수열은 앞의 두 수를 더해 다음 수를 만드는 수열입니다. 0, 1, 1, 2, 3, 5, 8, 13, ... 형태로, 두 번 자기 자신을 호출하는 다중 재귀의 대표 예제입니다.

fib(3)을 계산하려면 fib(2)와 fib(1)을 알아야 하고, fib(2)는 다시 fib(1)과 fib(0)을 호출합니다. 기저 조건(n <= 1)에 도달하면 멈춥니다. 그래서 fib(3) 한 번에 함수가 모두 5번 호출되고, fib(1)은 두 번 호출됩니다.

팩토리얼이 n * f(n-1)로 한 번 자기 자신을 호출한다면, 피보나치는 f(n-1) + f(n-2)로 두 번 호출한다는 점이 차이입니다. 다중 재귀 추적 방법은 아래 "실기 문제 풀이 전략"의 gamja 예제와 같습니다.

중첩 리스트 평탄화 예제

평탄화(flatten) 는 중첩된 구조를 한 겹으로 풀어 펴는 동작입니다. [1, [2, [3, 4]], 5]처럼 리스트 안에 리스트가 들어 있을 때, 재귀로 한 번씩 벗겨 내면 [1, 2, 3, 4, 5]로 만들 수 있습니다.

• isinstance(x, list)는 x가 리스트인지 확인하는 내장 함수입니다. 리스트가 아니면(숫자·문자열 등) 더 펼칠 것이 없으므로 [x]로 감싸 돌려줍니다.
• for item in x: result += flatten(item)은 각 요소를 다시 flatten에 넣어 얻은 리스트를 이어 붙여 하나로 모읍니다.

평탄화 + 합계를 한 번에 구하고 싶다면 sum(flatten(x)) 한 줄로 가능합니다.

실기 문제 풀이 전략 심화

재귀 함수 문제 풀이 순서

1. 기저 조건 확인: if문에서 어떤 값을 반환하는지 확인
2. 재귀 호출 파악: return문에서 자기 자신을 어떻게 호출하는지 확인
3. 호출 추적(호출 트리) 작성³: 기저 조건에 도달할 때까지 호출을 펼치기
4. 역순 계산: 기저 조건의 반환값부터 시작하여 위로 계산

복잡한 재귀: 두 번 이상 자기 자신을 호출하는 경우

재귀 호출이 두 번 이상 있는 경우, 각 호출의 반환값을 모두 계산해야 합니다.

이 함수는 gamja(n - 1)과 gamja(n - 3) 두 개의 재귀 호출을 합니다.

gamja(7) 호출 추적

기저 조건에 닿을 때까지 각 호출을 분해합니다. gamja(7)부터 시작하여 gamja(n - 1) + gamja(n - 3) 형태로 한 줄씩 펼쳐 내려가고, n <= 1인 기저 조건에 도달하면 멈춥니다. 왼쪽(n - 1)을 먼저 분해하고, 오른쪽(n - 3)은 나중에 분해합니다.

시험에서 풀 때, gamja(2)를 한 번 계산해 놓으면 다시 등장할 때 같은 값을 쓰면 됩니다. (실제 프로그램은 매번 다시 계산합니다.)

거꾸로 계산

모든 호출이 기저 조건에 도달했으므로, 가장 작은 값부터 거꾸로 계산합니다.

예를 들어 total(5) 재귀 함수는 다음 반복문과 같은 결과를 냅니다.

정보처리기사 실기 기출 문제