C언어 재귀함수 (Recursion)

재귀함수 핵심 정리

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

재귀함수란? 쌩기초

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

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

함수 호출 체인 기초

재귀를 이해하기 전에, 먼저 함수가 다른 함수를 호출하는 구조를 알아보겠습니다. 함수에서 배운 것처럼, 함수는 다른 함수를 호출할 수 있습니다.

이 코드는 재귀는 아니지만, 함수가 함수를 호출하는 체인 구조입니다.

호출 순서 추적하기

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

출력: 234

재귀함수의 동작 원리 기초

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

팩토리얼 예제

팩토리얼(Factorial)은 1부터 n까지의 모든 수를 곱한 값입니다. 5! = 5 x 4 x 3 x 2 x 1 = 120

재귀 호출 추적하기

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

1단계: 호출이 쌓이는 과정 (기저 조건에 도달할 때까지)

2단계: 반환값이 돌아오는 과정 (기저 조건에서부터 역순으로)

출력: 120

실기 문제 풀이 전략 심화

재귀함수 문제 풀이 순서

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

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

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

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

gamja(7) 호출 추적

gamja(7)부터 펼쳐 내려갑니다. 각 호출을 gamja(n-1) + gamja(n-3)으로 분해하고, 기저 조건(n <= 1)에 도달하면 멈춥니다.

같은 값이 여러 번 등장하지만, 한 번만 계산하면 나머지는 같은 결과입니다.

거꾸로 계산

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

gamja(7)의 출력: 2

정보처리기사 실기 대비 문제