재귀함수(Recursive call)

재귀함수는 자기 자신을 호출하는 함수이다

 

아래 코드의 SayHello()는 재귀함수이다

class Program
    {
        static void Main(string[] args)
        {
            SayHello();
        }

        static void SayHello()
        {
            SayHello();
        }
    }

단 재귀함수 호출 시 위의 예시처럼 호출 종료 조건을 정의하지 않으면

Stack 메모리에 콜스택이 무한대로 쌓여서 StackOverFlowError가 발생한다

이때 호출 종료 조건을 base condition이라고 부른다

 

아래는 재귀함수 개념을 적용해서 작성한 Factorial과 Fibonacci 수열을 구현한 함수이다

using System;

namespace Recursion
{
    class Program
    {
        static void Main(string[] args)
        {
            int factorial = Factorial(5); //120
            int fibonacci = Fibonacci(8); //21

            Console.WriteLine("Factorial(5)={0}\nFibonacci(8)={1}", factorial, fibonacci);
        }

        static int Factorial(int n)
        {
            //1*2*3*...*n
            if (n == 1) return 1;

            return n * Factorial(n - 1);
        }

        static int Fibonacci(int n)
        {   
            //1 1 2 3 5 8 13 21 ...
            if (n == 1) return 1;
            if (n == 2) return 1;

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