[recursion] 재귀 란 무엇이며 언제 사용해야합니까?

재귀는 분할 정복 사고 방식을 기반으로 문제를 해결하는 방법입니다. 기본 아이디어는 원래 문제를 가져 와서 더 작은 (더 쉽게 해결되는) 인스턴스로 나누고, 이러한 작은 인스턴스를 해결 한 다음 (일반적으로 동일한 알고리즘을 다시 사용하여) 최종 솔루션으로 재 조립하는 것입니다.

표준 예는 n의 계승을 생성하는 루틴입니다. n의 계승은 1과 n 사이의 모든 숫자를 곱하여 계산됩니다. C #의 반복 솔루션은 다음과 같습니다.

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

반복적 솔루션에 대해 놀라운 것은 없으며 C #에 익숙한 사람이라면 누구나 이해할 수 있습니다.

재귀 적 해는 n 번째 팩토리얼이 n * Fact (n-1)임을 인식하여 구합니다. 또는 다른 방법으로 말하자면, 특정 팩토리얼 숫자가 무엇인지 안다면 다음 숫자를 계산할 수 있습니다. 다음은 C #의 재귀 솔루션입니다.

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

이 함수의 첫 번째 부분은 Base Case (또는 때때로 Guard Clause) 로 알려져 있으며 알고리즘이 영원히 실행되는 것을 방지합니다. 함수가 1 이하의 값으로 호출 될 때마다 값 1을 반환합니다. 두 번째 부분은 더 흥미롭고 재귀 적 단계 로 알려져 있습니다. 여기서 우리는 약간 수정 된 매개 변수를 사용하여 동일한 메서드를 호출 한 다음 (1 씩 감소) 결과에 n의 복사본을 곱합니다.

처음 만났을 때 이것은 다소 혼란 스러울 수 있으므로 실행할 때 어떻게 작동하는지 조사하는 것이 좋습니다. FactRec (5)를 호출한다고 상상해보십시오. 우리는 루틴에 들어가고, 기본 케이스에 의해 선택되지 않으므로 다음과 같이 끝납니다.

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

매개 변수 4로 메소드를 다시 입력하면 다시 가드 절에 의해 중지되지 않으므로 다음과 같이됩니다.

// In FactRec(4)
return 4 * FactRec(3);

이 반환 값을 위의 반환 값으로 대체하면

// In FactRec(5)
return 5 * (4 * FactRec(3));

이렇게하면 최종 솔루션에 도달하는 방법에 대한 단서를 얻을 수 있으므로 아래로가는 각 단계를 빠르게 추적하고 보여 드리겠습니다.

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

최종 대체는 기본 케이스가 트리거 될 때 발생합니다. 이 시점에서 우리는 처음에 팩토리얼의 정의와 직접적으로 동일한 풀기위한 간단한 algrebraic 공식을 가지고 있습니다.

메서드를 호출 할 때마다 기본 사례가 트리거되거나 매개 변수가 기본 사례에 더 가까운 동일한 메서드에 대한 호출 (종종 재귀 호출이라고 함)이 발생한다는 점에 유의하는 것이 좋습니다. 그렇지 않은 경우 메서드는 영원히 실행됩니다.

답변

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}