C# 알고리즘 - 재귀호출(Recursive Call)

• 재귀호출(recursive call)이란?

재귀호출(recursive call)이란 함수 내부에서 자기 자신을 반복적으로 호출하는 것을 의미한다. 반복 행위를 하는 함수를 재귀함수(recursive function)라고 한다. 일반적인 상황에서는 잘 사용하지 않지만 알고리즘을 구현할 때 매우 유용하다. 알고리즘에 따라서 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 더 직관적이고 이해하기 쉽다. 복잡한 문제를 빠르고 쉽게 해결할 수 있다. 

 

- 팩토리얼(Factorial)

정규식

f(n) = n * (n-1)
//단, f(1) = 1
//5! = 5 x 4 x 3 x 2 x 1 = 120

public int FuncFactorial(int nNumber)
{
	int nResult = 0;
    
    if(nNumber == 1)
    {
    	nResult = 1;
    }
    else
    {
    	nResult = nNumber * FuncFactorial(nNumber - 1);
    }
    return nResult;
}

STEP1 : nResult = 5 x FuncFactorial(4);

STEP2 : nResult = 5 x 4 x FuncFactorial(3);

STEP2 : nResult = 5 x 4 x 3 x FuncFactorial(2);

STEP2 : nResult = 5 x 4 x 3 x 2 x FuncFactorial(1);

STEP5 : nResult = 5 x 4 x 3 x 2 x 1;

 

- 피보나치 수열(Fibonacci Sequence)

정규식

f(n) = 1 (n<=2)
f(n) = f(n-2) + f(n-1) (n>2)

public int Fibonacci(int nSequence)
{
	int nResult = 0;
    
    if(nSequence == 1 || nSequence == 2)
    {
    	nResult = 1;
    }
    else
    {
    	nResult = Fibonacci(nSequence - 1) + Fibonacci(nSequence - 2);
    }
    return nResult;
}

 

• 재귀호출(recursive call) 주의할 점

- 재귀호출은 반드시 중지되어야 한다. (기저 조건, 종료 조건)

- 재귀호출로 문제를 해결할 수 있는지 고민해야 한다. (스택 오버플로우 주의)

- 재귀함수는 시간복잡도를 줄일 수 있는 상황 또는 메모리 영역이 충분한 상황에서 사용해야 한다.

- 데이터는 스택에 채워진다.