C++
C ++에서 재귀

꼬리 재귀와 Fibonnaci 스타일 재귀를 사용하여 피보나시 시퀀스 해결

Fibonnaci 시퀀스의 N 번째 항을 얻기 위해 재귀를 사용하는 간단하고 가장 명백한 방법은 다음과 같습니다.

int get_term_fib(int n)
{
  if (n == 0)
    return 0;
  if (n == 1)
    return 1;
  return get_term_fib(n - 1) + get_term_fib(n - 2);
}

그러나이 알고리즘은 상위 용어로 확장되지 않습니다. n 이 커지면 함수 호출 수가 기하 급수적으로 커집니다. 이것은 간단한 꼬리 재귀로 대체 될 수 있습니다.

int get_term_fib(int n, int prev = 0, int curr = 1)
{
  if (n == 0)
    return prev;
  if (n == 1)
    return curr;
  return get_term_fib(n - 1, curr, prev + curr);
}

이제 함수를 호출 할 때마다 Fibonnaci 시퀀스의 다음 항이 즉시 계산되므로 함수 호출 수가 n 과 선형으로 늘어납니다.

메모로 재귀

재귀 함수는 꽤 비쌉니다. 함수가 순수한 함수 (동일한 인수를 사용하여 호출 할 때 항상 동일한 값을 반환하고 외부 상태에 의존하거나 수정하지 않는 함수) 인 경우 이미 계산 된 값을 저장하여 메모리를 희생시키면서 훨씬 빠르게 수행 할 수 있습니다.

다음은 memoization을 사용하여 피보나치 시퀀스를 구현 한 것입니다.

#include <map>

int fibonacci(int n)
{
  static std::map<int, int> values;
  if (n==0 || n==1)
    return n;
  std::map<int,int>::iterator iter = values.find(n);
  if (iter == values.end())
  {
    return values[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  else
  {
    return iter->second;
  }
}

간단한 재귀 공식을 사용 함에도 불구하고, 첫 번째 호출에서이 함수는 $ O (n) $입니다. 동일한 값을 가진 후속 호출에서는 물론 $ O (1) $입니다.

그러나이 구현은 재진입 적이 지 않습니다. 또한 저장된 값을 제거 할 수 없습니다. 또 다른 구현은지도가 추가 인수로 전달되도록 허용하는 것입니다.

#include <map>

int fibonacci(int n, std::map<int, int> values)
{
  if (n==0 || n==1)
    return n;
  std::map<int,int>::iterator iter = values.find(n);
  if (iter == values.end())
  {
    return values[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  else
  {
    return iter->second;
  }
}

이 버전의 경우 발신자는 저장된 값으로지도를 유지 관리해야합니다. 이 기능은 이제 함수가 재 호출 가능하고 호출자가 더 이상 필요하지 않은 값을 제거하여 메모리를 절약 할 수 있다는 이점이 있습니다. 캡슐화가 깨지는 단점이 있습니다. 호출자는 맵을 잘못된 값으로 채우면 출력을 변경할 수 있습니다.