[Tech, etc] Primitive recursive function(원시 재귀 함수)

 계산 가능성 이론(computability theory)에 따르면, 원시 재귀 함수는 대략적으로 반복문이 모두 "for"문인 컴퓨터 프로그램에 의해 계산되는 함수를 말한다. 원시 재귀 함수는 전역 함수(total function)이자 일반 재귀 함수들로 이뤄진 진부분집합(strict subset, proper subset)을 가진다. 원시 재귀 함수의 중요성은 수학에서 계산 가능한 대부분의 함수들이 원시 재귀라는 것에 있고, 더하기, 나누기, 팩토리얼, 지수 함수가 그 예다.

 

참고

- Primitivec recursive function(원시 재귀 함수): 반복 수를 알아 for loop 가능
- Recursive function(일반 재귀 함수): 반복 수를 몰라 for loop 불가 ex) 아커만 함수 (stack을 사용하여 해결 가능)

 

참조

- https://en.wikipedia.org/wiki/Primitive_recursive_function#Examples

- https://orubt.tistory.com/14