재귀 함수

Question

다음 요인 재귀 함수를 고려 수렴 여부를 결정한다. 그러나 음의 정수는 수렴하지 않습니다.

다음, 다음 프로그램을 고려 :

fact(n) = 
    if (n < 0) return 0 
    if (n = 0) return 1 
    return n * fact(n - 1) 

위의 함수는 모든 정수에 대한 수렴한다.

재귀 함수가 수렴되는지 여부를 정적으로 결정하는 방법을 알고 싶습니다.

Answer 1

는 그것은이다 좋은 점은 언어를 지정하지 않았고 제한없는 정수를 생각한다는 의미였습니다. 이는 웹 앱으로 this prototype analyzer for a toy language을 사용할 수 있음을 나타 내기 때문입니다.

제한되지 않은 정수를 사용하면 rici가 맞습니다. 이는 중단 문제입니다. 그러나 정적 분석기로 해결 된 대부분의 다른 문제는 정지 문제와 동일합니다. 그렇다고해서 문제의 정적 분석기가 유용하지는 않습니다. 그들은 거짓 부정, 거짓 긍정, 또는 두 가지 모두를 받아들임으로써 결정 불가능 성을 해결합니다.

C와 유사한 구문을 사용하려면 Frama-C의 값 분석을 사용하여 whether a simple C program terminates을 결정할 수 있습니다. 이 분석기는 재귀 함수를 처리하지 않으며 정수 유형을 바운드 형식으로 처리합니다. 제한된 정수형은 이론상 문제를 쉽게 만듭니다 (입력 언어의 정의에 따라 결정할 수 없게되지만).

Answer 2

일반적으로 사용자가 입력 할 수 없습니다. 그 질문은 바로 halting problem입니다. 여기

(이것은 모든 긍정적 인 n에 대한 중단한다는 주장이 Collatz conjecture이다) 꼬리 재귀 스타일로 작성 아마 긍정적 인 입력에 종료 재귀 함수의 간단한 예입니다 :

stop(n, a=0) = 
    if (n == 1) return a 
    if (n % 2 == 0) return stop(n/2, a + 1) 
    return stop(3 * n + 1, a + 1)