재귀 함수 (Recursive Function)

재귀 함수란?

재귀 함수란 어떤 함수 내부에서 자기 자신을 호출하는 함수로 이미 해결한 작은 문제에 더해서 더 큰 문제를 해결하는 방법이다.
재귀 함수를 사용하는 경우는 보통 반복문으로 해결하기 복잡한 문제를 재귀 함수로 작성하면 보다 쉽게 해결이 가능하다.
이 말은 모든 재귀 함수는 반복문으로 표현이 가능하는 뜻.

재귀적 해결법은 프로그래머의 논리력을 평가하기에 적합함.
실제로 최근 재귀 함수를 공부하고 연습하고 실습하는데 코드 몇 줄을 짜려고 꽤 오랜 시간 고민했다. (머리 깨질 뻔)

---

재귀 함수의 구성 요소

• 종료 조건(base case)
• 재귀적 함수 호출

---

종료 조건

종료 조건은 함수 호출을 멈추고 값을 반환하는 조건이다.
이 조건이 없으면 무한히 재귀 호출을 하다 Stack Overflow가 발생함.

---

재귀적 함수 호출

종료 조건이 아닌 경우 함수의 인자를 바꿔 스스로 다시 호출한다.

---

대표적인 재귀적 해결법

보통 팩토리얼, 피보나치 수열이 대표적인데 팩토리얼의 경우 자연수 1부터 n의 곱을 구한다.
이를 통해 종료 조건을 작성할 수 있으며 종료 조건을 만족할 경우 n을 반환하여 재귀 호출을 멈춘다.

이와 같이 간단한 재귀 함수를 이용한 해결은 쉽지만 조금 더 복잡한 문제를 재귀 함수를 사용하여 풀기 위해선 꽤나 많은 고민이 필요하다.
이번에 재귀 함수를 공부하면서 생각보다 어려웠고 처음으로 느끼는 답답함을 느꼈다. 그래서 더 재귀 함수를 많이 공부했다.
앞으로도 꾸준히 논리적으로 생각하는 방법을 연습해야겠다.

static void Main(string[] args)
        {
            Console.WriteLine($"Factorial: {FactorialRecursive(5)}");
            Console.WriteLine($"Fibonacci: {FibonacciRecursive(10)}");
        }

        static int FactorialRecursive(int n)
        {
            if (n == 1)
            {
                return n;
            }

            return n * FactorialRecursive(n - 1);
        }

        static int FibonacciRecursive(int n)
        {
            if (n <= 1)
            {
                return n;
            }

            return FibonacciRecursive(n - 2) + FibonacciRecursive(n - 1);
        }