📒 갈무리 - 재귀호출(Recursive call)

📌 재귀호출이란?

- 함수 내부에서 자기 자신을 반복적으로 호출하는 것을 의미한다.

- 끝나는 조건을 설정하지 않으면 끝나지 않는다.

- 일반적인 상황보다는 알고리즘을 구현할 때 데이터 흐름을 파악하고자 할 때 사용한다.

- 알고리즘에 따라서 일반 반복문 보다 재기호출로 구현한 코드가 더 이해가 쉬울 때가 있다.

- 재귀호출을 사용하게 되면 코드가 간결해진다는 장점이 있지만, 성능상 비효율적이다.

 

📌 직접 구현해 보자...

ex) Factorial

// C# Factorial 구현

    class Program
    {
        private const int FACTORIAL_NUMBER = 5;
        static void Main(string[] args)
        {
            int answer = Factorial(FACTORIAL_NUMBER); // FACTORIAL_NUMBER 팩토리얼을 구함
            Console.WriteLine(answer); // 120을 출력
            Console.ReadLine();
        }
        
        // Factorial에서 음수는 정의되지 않기 때문에 고려하지 않음(음의 정수에 근접하면 양의 무한대로 발산)

        static public int Factorial(int value)
        {
            int answer = value;
            if (value <= 1) 
            {
                return 1;
            }
            return answer *= Factorial(--value);
        }
    }

 

ex) 피보나치수열(Fibonacci Sequence)

// C# 피보나치수열 구현

    class Program
    {
        private const int FIBONACCI_NUMBER = 10;
        static void Main(string[] args)
        {
            int answer = Fibonacci(FIBONACCI_NUMBER); // FIBONACCI_NUMBER번째의 피보나치 수열을 구함

            Console.WriteLine(answer); // 55 출력
            Console.ReadLine();
        }

        static public int Fibonacci(int value)
        {
            if (value <= 2)
            {
                return 1;
            }

            return Fibonacci(value - 1) + Fibonacci(value - 2);
        }

        // 사실 피보나치수열은 재귀호출로 구현하게 되면 굉장히 비효율적인데,
        // 다이나믹 프로그래밍 기법을 사용하여 효율성을 늘릴 수 있다.
    }

 

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

재귀호출을 구현할 때 반드시 중지되는 조건을 구현하여야 한다.(기저 조건, 종료 조건)

재귀호출로 문제를 해결할 수 있는지 잘 고민해 보아야 한다.(Stack Overflow 주의)