6.5 재귀, 하나 더
우리가 지금까지 다룬 내용은 파이썬의 일부분이지만, 이것만으로도 완전한 프로그래밍 언어이고, 계산할 수 있는 것이라면 무엇이든 이 언어로 표현할 수 있다면 흥미롭지 않은가? 지금까지 작성된 어떤 프로그램도 지금까지 배운 언어 기능만으로도 재작성할 수 있다(물론, 마우스, 디스크 같은 기기를 다루는 몇 가지 명령어는 더 배워야 하지만, 그 정도면 충분하다).
이 주장을 처음 입증한 것은 최초의 컴퓨터 과학자 중에 한 명인 앨런 튜링이 처음으로 해결한 작은 연습문제였다(앨런 튜링이 수학자였다고 주장하는 사람도 일부 있지만, 초기 컴퓨터 과학자들은 대부분 수학자로 시작했다). 이런 이유로 이 연습문제는 튜링 명제(Turing Thesis)로 알려져 있다. 튜링 명제에 대한 더 자세한(그리고 더 정확한) 설명을 원한다면 <Introduction to the Theory of Computation 3rd Ed.>(Michael Sipser, Course Technology, 2012)를 추천한다.
여러분이 지금까지 학습한 도구로 무엇을 할 수 있는지 알려주기 위해 몇 가지 수학 함수를 재귀적으로 평가해보겠다. 정의 안에 정의하고 있는 것에 대한 참조를 담고 있다는 점에서 재귀적인 정의는 환원적인 정의와 비슷하다. 그러나 진짜로 환원적인 정의는 그렇게 유용하지 않다.