[유니티 / C#] 재귀함수(Recursive Function)

재귀함수

재귀함수는 함수 내부에서 자기 자신을 호출하는 함수를 뜻합니다.

보통 큰 문제를 작은 부분 문제로 나누어 해결할 때 자주 사용합니다.

예를 들어 팩토리얼, 피보나치 수열, 트리 탐색 등의 알고리즘을 해결할 때 재귀함수를 사용하여 해결할 수 있습니다.

재귀함수는 보통 두 부분으로 나누어집니다.

1. 기저 조건(Base Case) - 재귀를 멈추는 조건

2. 재귀 호출(Recursive Call) - 자기 자신을 다시 호출

static void Factorial(int n)
{
    if(n <= 1) return 1;		//기저 조건
    return n * Factorial(n - 1);	//재귀 호출
}

1. 자기 자신을 호출

재귀함수는 함수 내부에서 자기 자신을 호출합니다. 이를 통해 반복적인 작업을 수행할 수 있습니다.

2. 기저 조건이 반드시 필요

재귀함수는 기저 조건을 올바르게 작성하지 않으면 무한히 자기 자신을 호출하며 스택 오버플로우가 발생합니다.

3.스택 메모리를 사용

함수가 호출될 때마다 스택에 쌓이게 됩니다. 따라서 재귀가 깊어질수록 메모리 사용량이 증가합니다.

4. 재귀 함수의 성능

반복문에 비해 코드가 간결합니다. 하지만 함수 호출이 계속 일어나기 때문에 성능이 떨어질 수 있습니다.

재귀함수를 호출하는 횟수가 많을 경우에는 오히려 반복문 + 스택 자료구조를 사용하는 것이 효율적일 수 있습니다.

스택 프레임(Stack Frame)

메모리의 스택(Stack) 영역은 함수의 호출에 필요한 지역변수와 매개변수가 저장되는 영역으로

함수의 호출과 동시에 할당되며, 함수의 호출이 끝나면 소멸됩니다.

이 과정에서 스택 영역에 차례대로 저장되는 함수의 호출 정보를 스택 프레임(Stack Frame) 이라고 합니다.

재귀함수는 자기 자신을 반복해서 호출하는 함수로 자신을 호출할 때 마다 스택 메모리에 정보를 저장하고

기저 조건을 만나 함수가 종료될 때 스택에서 함수 정보를 Pop하게 됩니다.

하지만 기저 조건이 없는 등의 경우로 무한히 호출하게 될 경우 스택에 계속 저장되고 메모리의 용량을 넘어가는 순간

스택 오버플로우가 발생하게 될 것입니다.

따라서 재귀 함수를 이용할 때는 반드시 무한 호출이 발생하지 않도록 유의해야 합니다.

또한 이 과정에서 자기 자신을 호출할 때 발생하는 비용이 생각보다 크기 때문에 반복문을 사용하는 것을 고려해보는 것이 좋습니다.