C# - 재귀 함수(Recursive Function)

재귀 함수(Recursive Function)

• 이미 해결한 작은 문제에 더 큰 문제를 해결하는 방법
• 프로그래밍에서는 함수 A가 매개변수만 바꾸어 다시 함수A를 호출하는 방법으로 구현

recursive(형용사): 반복되는

static uint SumRecursive(uint num)
{
	if (num == 0)
    {
    	return 0; // 종료조건 (base case)
    }
    else
    {
    	return num + SumRecursive(num -1);
        // 재귀 호출 (recursive function)
    }
}

static void Main(string[] args)
{
	Console.WriteLine(SumRecursive(3));
}

재귀 함수의 구성요소

• 종료조건 (ending condition, base case)
  • 더 이상 재귀 함수를 호출하지 않고 값을 반환하는 조건
  • 매우 간단히 함수의 반환 값을 찾을 수 있는 경우
  • 이것이 없으면 무한루프에 빠진다.
• 재귀적 함수 호출
  • 종료조건이 아닌 경우
  • 함수의 인자를 바꿔 스스로를 다시 호출
  • 이 때, 함수의 인자는 현재 문제보다 작은 문제를 대표해야함
  • 즉, 동일한 동작을 보다 작은 문제에 적용

반복문과의 비교

• 모든 재귀 함수는 반복문으로 해결 가능
• 복잡한 문제일수록 재귀 함수가 더 편함
  • 이진 검색
  • 트리 구조
  • 퀵 정렬
  • 하노이의 탑
  • 어떤 폴더 아래에 있는 모든 파일 목록 구하기

피보나치 수열 (Fibonacci)

• 제 0항은 0, 제 1항은 1이며, 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열

0 1 1 2 3 5 8 13 21 34 55 ...

• 수학적 정의
  • F₀ = 0
  • F₁= 1,
  • Fₙ = Fₙ-1 + Fₙ-2, (n > 1)

using System;

namespace _Fibonacci
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write(Fibonacci(5)); 
        }

        static uint Fibonacci(uint number)
        {
            if (number == 0)
            {
                return 0;
            }
            if (number == 1)
            {
                return 1;
            }
            return Fibonacci(number - 1) + Fibonacci(number - 2);
        }
    }

• 함수는 신뢰의 문제
• 재귀 함수는 더 큰 신뢰를 요구

재귀적 해결법 = 논리력

• 프로그래머의 논리력을 평가하기에 적합
• 매우 큰 문제를 작게 쪼개서 증명할 수 있나
  • 절대 틀릴 수 없는 최소한의 문제를 품
  • 최소한 문제의 해법에 의존하여 그 보다 하나 더 큰 문제를 해결
  • 그 과정을 반복하면 논리적으로 최종 문제까지 해결
• 수학적 귀납법과 매우 밀접

하노이의 탑으로 이해하는 재귀 함수

• 막대 세 개가 있고, 한 막대에 n개의 원판이 있음

  • n개의 원판에서 상위 n-1개를 다른 막대에 옮길 수 있다고 가정
    • n-1개의 원판을 중간 막대로 옮김
    • 마지막 n번째 원판은 목적지 막대에 옮김
    • 중간 막대에 있던 n-1개의 원판을 목적지 막대에 옮김

• 막대 세 개가 있고, 한 막대에 n-1개의 원판이 있음

  • n-1개의 원판에서 상위 n-2개를 다른 막대에 옮길 수 있다고 가정
    • n-2개의 원판을 중간 막대로 옮김
    • 마지막 n-1번째 원판은 목적지 막대에 옮김
    • 중간 막대에 있던 n-2개의 원판을 목적지 막대에 옮김

• 막대 세 개가 있고, 한 막대에 2개의 원판이 있음

  • 2개의 원판에서 상위 1개를 다른 막대에 옮길 수 있다고 가정
    • 1개의 원판을 중간 막대로 옮김
    • 마지막 2번째 원판은 목적지 막대에 옮김
    • 중간 막대에 있던 1개의 원판을 목적지 막대에 옮김

• 막대 세 개가 있고, 한 막대에 1개의 원판이 있음

  • 1개의 원판을 다른 막대에 옮길 수 있음
    • 1개의 원판을 목적지 막대로 옮김
    • 종료 조건이 참이므로 위의 모든 과정이 참이 됨

재귀 함수의 장점

• 개념적으로 매우 훌륭함
• 증명이 가능함

재귀 함수의 단점

• 효율성이 떨어짐
• 반복문은 그런 문제가 없음: 이전 연산의 결과를 저장(캐싱)하기 때문
• 스택오버플로우 (Stack Overflow)
  • 함수 호출 깊이에는 제한이 있음

베스트 프랙티스

• 캐싱 없이 간단한 반복문으로 작성 가능한 문제는 반복문으로
  • 예: 1~N까지 수의 합 구하기
• 그 외에는 재귀 함수로 우선 작성
  • 설계 및 이해가 용이하기 때문
• 다음의 경우에는 반복문으로 코드 리팩토링(code refacktoring)
  • 함수 호출의 최대 깊이를 확정할 수 없음
  • 또는, 성능상의 문제를 발견

재귀 팩토리얼(factorial)

using System;

namespace _20210327
{
    class Program
    {
        static void Main(string[] args)
        {
            const ulong FACTORIAL = 10;
            Console.Write("NonRecursiveFactorial: ");
            Console.WriteLine(NonRecursiveFactorial(FACTORIAL));

            Console.Write("RecursiveFactorial: ");
            Console.WriteLine(RecursiveFactorial(FACTORIAL));
        }
        static ulong NonRecursiveFactorial(ulong n)
        {
            if (n <= 1)
            {
                return 1;
            }
            uint factorial = 1;

            for (uint i = 2; i <= n; i++)
            {
                factorial *= i;
            }

            return factorial;
        }

        static ulong RecursiveFactorial(ulong n)
        {
            if (n==0)
            {
                return 1;
            }
            return RecursiveFactorial(n - 1) * n;
        }
    }
}