재귀 세트 대 재귀 함수

StackOverflow https://stackoverflow.com/questions/1853409

문제

재귀 세트와 재귀 함수의 차이점은 무엇입니까?

도움이 되었습니까?

해결책

재귀 함수 및 재귀 세트는 계산 가능성 이론에 사용되는 용어입니다. Wikipedia는 다음과 같이 정의합니다.

일련의 자연 숫자는 N 숫자 N이 세트에 있고 정지 된 경우 출력 1이 1 중지되는 튜링 머신이있는 경우 계산 가능한 세트 (결정 가능한, 재귀 또는 튜링 컴퓨팅 가능 세트라고도 함)라고합니다. N이 세트에없는 경우 출력 0으로. 입력 n에 출력 f (n)를 정지하고 반환하는 튜링 머신이있는 경우 자연 숫자에서 자연 숫자로부터의 함수 f는 재귀 적 또는 (turing) 계산 가능 함수이다.

이러한 맥락에서 재귀 함수가 자신을 호출하는 프로그래밍 언어의 함수를 의미하지는 않습니다. 어느 매우 정확한 위의 정의의 요구 사항을 충족하는 함수는 ID 함수 또는 모든 숫자를 1에 1에 매핑하는 기능을 포함하여 재귀 함수입니다 (즉, 입력에 관계없이 숫자 1을 반환).

다른 팁

이 용어의 의미는 컨텍스트에 따라 다릅니다. 우리가 프로그램 작성의 관점에서 순전히 논의했다면 재귀 세트 이해하지 못합니다. 그러나 아직 만난 적이있을 수 있습니다. 즉, 재귀 함수 실행에서 자신을 부르는 기능입니다. an의 계산th 피보나치 번호 일반적으로 제시되는 전형적인 예입니다.

/// <summary>A C# implementation of a function to return the nth Fibonacci number.</summary>
private static int Fibonacci(int n) {
 if (n <= 2) {
  return 1;
 } else {
  return Fibonacci(n - 1) + Fibonacci(n - 2);
 }
}

즉, 컴퓨터 과학의 맥락에서, 특히 계산 이론에서 이러한 용어에 대한 다른 맥락은 공식 언어. 이러한 맥락에서, a 재귀 세트 해결 가능한 멤버십 문제가있는 세트로 정의됩니다. 예를 들어, 우리는 자연 번호 ℕ 재귀 함수를 다음과 같이 정의 할 수 있기 때문에 재귀 세트입니다.

허락하다 에프 다음의 함수로 정의됩니다 f (x) = 1 만약에 x ∈ ℕ 그리고 f (x) = 0 만약에 x ∉ ℕ

재귀 세트의 개념은 계산 가능성의 개념에 중요합니다. 재귀 적으로 열거 가능한 세트 이것은 튜링 머신 (즉 튜링-인식 가능). 이들은 튜링 머신이 주어진 문자열이 언어의 구성원인지 판단 할 수있는 언어입니다. 즉, 기계가 둘 중 하나 일 수 있습니다. 동의하기, 거부하다, 또는 고리. 이것은 a와 대조적입니다 튜링을 유발할 수 있습니다 기계가 동의하기 또는 거부하다 주어진 입력 문자열에 대한 상태.

이것은 a의 개념이있는 곳입니다 재귀 기능 재귀 함수 (또는 총 재귀 함수)는 튜링 머신에 의해 계산 될 수 있고 모든 입력에 대해 정지 할 수 있으므로 재생됩니다. 부분 재귀 함수로서 동작 중단과 관련하여 보장없이 튜링 머신에 대해서만 계산할 수 있습니다. 또는 본질적으로 재귀 함수는 재귀 세트의 대응이다.

따라서 계산 이론의 맥락에서 원래 질문으로 돌아 오기 위해 재귀 세트는 생성 될 수있는 것 (즉, 열거 된) 또는 튜링 머신의 재귀 기능에 의해 멤버십을 테스트 할 수 있습니다.

추가 읽기 :

아마도 질문은 "왜 '재귀라는 단어가 세트와 기능을 모두 설명하는 데 사용 되는가?"였을 것입니다.

Greg Hewgill이 그의 의견에서 지적했듯이, '녹색'이라는 단어는 사과와 자동차에 적용될 수 있지만 사과와 자동차 사이의 관계를 의미하지는 않습니다.

Wikipedia의 인용문은 '재귀'라는 용어를 'Computable'과 동의어로 사용한다고 생각합니다. 프로그래머로서 특정 상황에서만 조심스럽게 동의 할 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top