3장-5. 재귀 함수

재귀란 무엇인가?

• for문이나 while문 이외에 반복을 구현하는 또 다른 방법
• 자신의 정의 내에서 자기 자신을 호출하는 것
• 재귀는 반복적인 작업을 수행하는데 명쾌하고 강력한 대안을 제시한다!

 

 

---

계승 함수

• 양의 정수 n의 계승(n!)는 1부터 n까지의 정수곱이다.
• n = 0이라면 n!는 1로 정의된다.
• 더 일반적으로는 n >= 0이다.

 

5! = 5 x 4 x 3 x 2 x 1 = 120
이런 n!를 나타내기 위해 factorial(n) 이라는 표현을 사용한다.

 

• 계승 함수는 재귀적인 공식을 제시하는 방법으로도 정의된다.

factorial(5) = 5 * (4 * 3 * 2 * 1) = 5 * factorial(4)

• 그래서 일반적으로 양에 정수에 대해 factorial(n)은 n * factorial(n-1)로 표기할 수 있다.

 

 

 

---

재귀 함수

• 재귀 함수는 하나의 기저 사례를 포함함. (factorial 예제에서는 0이 기저 사례)
• 따라서 재귀 함수에는 기저 사례와 재귀 사례 두 가지로 나뉜다.
• 재귀 사례는 다시 변화된 인수를 가지고 자신을 호출하는 것.

int recursiveFactorial(int n)
{
	if (n == 0) return 1;
	else return n * recursiveFactorial(n - 1);
}

• 대표적인 factorial 예제.

 

재귀 함수를 쉽게 이해하는 방법

• 이후에 나올 예제들을 살펴보면 재귀 함수가 어떤 흐름을 띄는지 이해하기가 매우 어렵다.
• 따라서 재귀함수를 이해하려면 비유를 통해서 이해해야 한다.
• 어떤 블로그에 포스팅 된 글을 참고하였다.
• https://www.secmem.org/blog/2021/07/09/recursion/

재귀 함수에 대한 이해

 

1. 프로그램이 실행되는 과정을 생산 라인에서 여러 직원들이 제품 생산하는 과정이라고 하자
2. 프로그램 입력은 제품의 재료
3. 소스 코드는 직원들의 매뉴얼
4. 직원은 매뉴얼에 적힌 내용대로 실제로 일을 하는 주체
5. 소스 코드는 그저 매뉴얼에 불과하므로 같은 매뉴얼대로 작업하는 직원은 여럿이 될 수 있다.
6. 하나의 매뉴얼이라 하더라도 세부적인 작업 내용은 직원이 넘겨 받은 재료에 따라 다를 수 있다

 

즉, 재귀 호출은 한 직원이 자신과 같은 매뉴얼에 따라 작업하는
다른 직원에게  특정 상태의 재료를 건네며 작업을 요청하고, 그 결과물을 돌려받는 과정.

 

 

 

 

---

 

재귀 추적

• 재귀 추적을 사용하면 재귀 함수 정의가 실행되는 것을 도식적으로 표시할 수 있다.
• 새로운 재귀 함수 호출은 화살표로 가리킨다.
• 리턴은 휘어진 화살표로 가리키고 리턴 값은 그 화살표 옆에 위치시킨다.

 

factorial(5)의 재귀 추적

 

 

 

 

 

 

---

예제: 영국식 자 그리기

• 영국식 자는 간격들로 구분되고, 각 간격은 1/2인치, 1/4인치 등의 등간격으로 놓은 표식의 집합
• 가장 긴 표식의 길이를 주요 표식 길이라고 부른다.
• 중심 표식이 L이면 위 아래 표식의 크기가 L-1로 같다는 것을 이용해야 한다.

 

#include <iostream>
using namespace std;

void drawOneTicks(int tickLength, int tickLabel = -1)
{
	for (int i = 0; i < tickLength; i++)
	{
		cout << "-";
	}

	if (tickLabel >= 0) cout << " " << tickLabel;
	cout << "\n";
}

void drawTicks(int tickLength)
{
	if (tickLength > 0)
	{
		drawTicks(tickLength - 1);
		drawOneTicks(tickLength);
		drawTicks(tickLength - 1);
	}
}

void drawRuler(int nInches, int majorLength)
{
	drawOneTicks(majorLength, 0);
	for (int i = 1; i < nInches; i++)
	{
		drawTicks(majorLength - 1);
		drawOneTicks(majorLength, i);
	}
}

int main()
{
	drawRuler(2, 5);
}

• drawOneTicks 함수는 주어진 값에 따라 그려주는 유틸리티 함수
• drawTicks는 재귀적으로 자신과 drawOneTicks를 호출하여 자를 그려주는 함수
• drawRuler는 drawTicks의 초기값을 전달해주는 함수