재귀 (Recursion)

재귀(Recursion)란 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘이다. 재귀 함수는 전달되는 매개변수만 달라질 뿐 똑같은 일을 수행한다.

큰 문제를 부분 문제로 쪼개서 해결할 때 유용하다.

재귀 함수는 일반적인 수학의 점화식을 그대로 표현가능한 능력을 가지고 있어, 프랙탈, 분할 반복 등에서 유용하게 사용할 수 있다.

다음 코드의 NumCount 함수는 매개변수 Num 이 1 일때를 제외하고 매개변수로 받은 Num 의 -1 을 인자로 다시 NumCount 함수를 호출하는 코드이다.

#include <iostream>

void NumCount(int Num)
{
	std::cout << "Num : " << Num << std::endl;

	if (1 != Num)
	{
		NumCount(Num - 1);
	}
}

int main() 
{
	NumCount(5);

	return 0;
}

Num : 5
Num : 4
Num : 3
Num : 2
Num : 1

위의 코드는 다음과 같은 흐름으로 진행된다.

이처럼 재귀 함수는 유용하게 사용할 수 있는 로직이지만 함수를 호출하는데 비용이 발생하기 때문에 무작정 사용하는것은 좋지 않다. 재귀 함수를 이용하는 문제는 대부분 반복문으로도 해결 가능하다.

또한 재귀 함수를 이용할때는 무한루프를 돌지 않도록 반드시 탈출조건을 명시해야하며 무한루프를 돌지 않더라도 스택오버플로우가 발생하지 않도록 주의해야한다.

예시

팩토리얼

#include <iostream>

int Factorial(int Num)
{
	if (1 == Num)
	{	
		std::cout << Num << " = ";
		return 1;
	}
	else
	{
		std::cout << Num << " * ";
		return Num * Factorial(Num - 1);
	}
}

int main() 
{
	std::cout << Factorial(5);
	return 0;
}

5 * 4 * 3 * 2 * 1 = 120

피보나치 수열

F(N) = F(N - 2) + F(N - 1), (N > 1)

#include <iostream>

int Fibonacci(int Num)
{
	if (1 >= Num)
		return Num;

	return Fibonacci(Num - 1) + Fibonacci(Num - 2);
}

int main() 
{
	std::cout << Fibonacci(5);
	return 0;
}

5