[C#] Recursion Function

재귀 함수

---

재귀 함수란?

static int Factorial(int n)
{
    if (n == 0)
    {
        return 1;
    }
    return n * Factorial(n - 1);     // 재귀 함수 호출 
}

위의 코드는 팩토리얼 연산을 함수로 구현한 것으로, Factorial 함수를 새롭게 정의하고 있지만 그 내용에 Factorial 함수가 사용(호출)되는 것을 볼 수 있다. 이렇게 함수에서 함수 자신을 호출하는 것을 재귀 또는 재귀 함수라고 한다.

• 특징

  재귀 함수는 작업을 쪼개서 처리한 결과를 결합하는 방법으로 해결한다. 따라서 반복에 비해 더 짧게 구현이 가능하여 함수라는 특징에 적합하지만, 이를 설계하는 것과 확인하는 테스트 과정에서 난이도가 더 높다.
  

• 장점

  1. 다양한 변수가 필요없다. 현재 상태를 저장하기 위해 임시 변수(temp)을 만들지 않고 함수를 재귀 호출하면서 전달하는 것이 가능하다.
  2. 코드가 간결하여 가독성이 좋다.

• 단점

  1. 지속적으로 함수를 호출하여 이때마다 지역변수, 매개변수, 반환주소값을 스택에 저장한다. 이런 과정은 임시 변수를 사용하는 반복문에 비해 메모리를 더 많이 사용하며, 컨텍스트 스위칭 과정으로 인해 속도 저하가 발생한다.
  2. 스택 오버플로우가 발생할 위험이 있다.

재귀함수의 장단점과 해결책

과제

재귀 함수를 사용하지 않고 피보나치 수열을 구현

static int Fibonacci(int input)
{
    int sum1 = 0;
    int sum2 = 1;
    int temp;

  	temp = sum2;
	sum2 = sum2 + sum1;
	sum1 = temp; 
  	
    return sum1;
}

피보나치 수열 : 첫 번째 및 두 번째 항이 1이고, 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열

먼저 구현을 위해 값이 0인 가상의 0번째 항을 추가하여 두 번째 항을 0번째 항과 첫 번째 항의 합으로 표현을 해주었다.

따라서 0번째 항과 첫 번째 항의 값을 선언과 동시에 부여하고, 다음 항이 앞 두 항의 합이라는 수식을 추가하면 피보나치 수열의 기본 규칙을 만족시킨다.

다만, 기존의 sum2 값을 sum1에 부여해야하는데, sum2 값이 초기화되기 때문에 임시 변수 temp를 추가하여 연산 전 num2의 값을 저장하도록 설계했다.

재귀 함수를 사용하여 피보나치 수열을 구현

static int Fibonachi(int n)
{
    if(n == 2 || n == 1)
    {
        return 1;
    }
    return Fibonachi(n-1) + Fibonachi(n-2);
}

구현을 위해 첫 번째 항과 두 번째 항의 값을 1로 미리 정해놓고, 피보나치 수열의 규칙을 재귀 함수를 호출함으로써 작성했다.

이처럼 재귀함수를 사용하면, 초기 조건과 규칙을 명확히 설정하면 더 간결하게 기능을 구현하는 것이 가능하다.

다만, 구현한 두 코드를 실행했을 때 입력값이 작으면 속도 차이가 크게 나지 않지만, 입력값이 커짐에 따라 재귀함수의 처리속도가 훨씬 더 느리다는 것이 체감된다.