C# - 재귀함수 (Recursive Function)

재귀함수 (Recursive Function)

재귀함수란 자기 자신을 다시 호출하는 함수를 말한다.

보통 함수는 호출되면 어떤 동작을 수행하고 끝나지만, 재귀 함수는 함수 내부에서 자기 자신을 다시 부른다.

static void ReFunc()
{
	// 어쩌고 저쩌고 조건, 다른 로직 등등
    // . . .
    // . .
    Refunc(); 			// Refunc() 함수 안에서 ReFunc() 함수를 다시 호출한다
}

 

재귀함수를 사용할 때 주의점은 종료 조건을 제대로 정의하는 것이다.

이게 제대로 정의되지 않으면 무한 루프 지옥에 빠져버린다.

만약 서버 로직 같은 걸 무한 호출 시켜버리면 바로 그냥 진실의 방으로 가는 거니까 조심하자.

 

재귀함수는 함수 안에서 특정 조건 안에서 과정이 반복되면서 문제를 점점 더 작은 단위로 쪼개 해결하는 구조를 가진다.

작은 문제를 풀 수 있다면, 큰 문제도 같은 방식으로 풀 수 있다 라는 사고가 재귀 함수의 본질이라고 한다.

 

그래서 이걸 도대체 어디에, 왜 쓰는데??

라고 질문 할 수 있다.

답은 간단하게도 문제의 정의 자체가 재귀적인 경우에 사용한다.

문제의 정의가 재귀적이다라고 하니 이게 무슨 소리인가 싶지만 우리는 중, 고등학교 때 이미 자기 자신을 포함하며 로직을 완성해나가는 경우를 본 적 있다.

바로 대표적인게 팩토리얼, 피보나치 수열 이다.

이렇게 연산시 자기 자신을 포함하고, 자기 다음에 올 연산 또한 자기 자신을 포함해야하는 형태가 반복되는 구조다.

 

우선 그럼 말이 나온 김에 팩토리얼과 피보나치 수열을 코드로 구현해보자

using System;

class Program
{
    static void Main()
    {
        Console.WriteLine(Factorial(5)); // 출력: 120
    }

    static int Factorial(int n)
    {
        if (n == 0) // 종료 조건
            return 1;
        else
            return n * Factorial(n - 1); // 재귀 호출
    }
}

 

팩토리얼 함수의 내용을 보자.

응? 이것만 보면 처음 본 사람은 그래서 대체 이게 뭐 어쩌란 거냐? 고 생각 할 수 있다.

하지만 이걸 풀어해쳐보면 별거 아닌 구조다.

 

Factorial(n) 함수가 리턴 될 때 n * Factorial(n-1) 함수가 리턴된다.

그럼 이걸 또 풀면 n * (n-1) * Factorial(n-2) 함수가,

또 풀어내면 n * (n-1) * (n-2) * Factorial(n-3) 함수가 끝없이 반복 될 거다.

언제까지?

n==0이 되는 종료조건이 충족될 때까지

n에 5를 대입해보면

Factorial(5) * Factorial(4) * Factorial(3) * Factorial(2) * Factorial(1) * Factorial(0)

이렇게 호출될 것이고 n==0 이라는 조건을 기준으로 Factorial(n)은 n, Factorial(0)은 1을 리턴하므로 결과적으로

5 * 4 * 3 * 2 * 1 * 1

라는 연산을 수행할 것이다.

이렇게 간단하게 우리가 알고있는 5! 와 동일한 식이 완성됐다.

 

 

피보나치 수열도 확인해보자

이전 글에서 피보나치 수열을 다른 방식으로 구현했지만, 내부의 수를 변수에 넣고 재활용하는 방식은 사실 재귀함수랑 본질적으로 다르지 않다.

피보나치 수열을 코드로 구현하면 다음과 같다

using System;

class Program
{
    static void Main()
    {
        for (int i = 0; i < 10; i++)
        {
            Console.Write($"{Fibonacci(i)} ");
        }
        // 출력: 0 1 1 2 3 5 8 13 21 34
    }

    static int Fibonacci(int n)
    {
        if (n == 0) return 0; // 종료 조건 1
        if (n == 1) return 1; // 종료 조건 2

        return Fibonacci(n - 1) + Fibonacci(n - 2); // 재귀 호출
    }
}

 

여기서는 이전 문제와 다르게 피보나치 수열을 0부터 시작하게 정의했다.

X(n) = X(n-1) + X(n-2) 라고 이전 글에서도 정의하고 시작한 적 있다.

오잉? 이렇게 보니까 위 재귀함수와 완전한 동일한 형태 아닌가?

 

Fibonacci(10) = Fibonacci(9) + Fibonacci(8) 이 된다

그럼 이게 도대체 어떻게 실제 숫자가 되는 건지 한 눈에 바로 알기 어려울 수 있다.

 

답은 역시나도 간단하게도 함수 내에서 정의해둔

if (n == 0) return 0;

if (n == 1) return 1;

이 두 종료 조건 때문이다.

 

편의를 위해 F(5)라고 작성하겠다.

F(5)

F(4) + F(3)

F(3) + F(2) + F(2) + F(1)

F(2) + F(1) + F(1) + F(0) + F(1) + F(0) + 1

F(1) + F(0) + 1 + 1 + 0 + 1 + 0 + 1

= 5

 

이렇게 분해해서 보면 아주 간단하게 이해할 수 있다.

 

이렇게 보니까 정말 별거 아니어 보이지만 이런 대표적인 문제 외에도 더 복잡한 문제를 푸는데에 재귀함수는 간혹 사용될 것이다.

익숙해진다면 수학적 정의를 정확하게 표현할 수 있어서 이해하기 쉬워지고 코드가 깔끔해진다.

 

하지만 사용에는 반드시 주의가 필요하다.

함수 호출이 계속 쌓이므로 메모리 스택을 많이 사용하며, 종료 조건을 잘못 정의하면 무한 재귀 루프에 빠져서 스택오버플로우를 발생시키게 된다.

잘못하면 진실의 방 행이다.

 

위의 팩토리얼과 피보나치 같은 경우는 재귀함수로 표현할 수 있는 대표적인 예지만 단순한 반복문이나 수학적 표현을 통해 구현할 수 있다면 그게 훨씬 안정적이고 성능적으로도 빠르기에 항상 재귀함수가 좋은 해결책인 건 아니다..

 

 

그 외에도 트리탐색, 그래프 탐색 등 복잡한 반복문을 재귀로 표현해 코드를 단순화하여 직관적으로 표현하기 위해서도 사용하며

알고리즘에서도 DFS(깊이 우선 탐색), 분할 정복(Divide and Conquer), 백트래킹, 퀵소트, 합병 정렬 등에서 사용될 수 있다.