더북(TheBook)

6.5 재귀, 하나 더

우리가 지금까지 다룬 내용은 파이썬의 일부분이지만, 이것만으로도 완전한 프로그래밍 언어이고, 계산할 수 있는 것이라면 무엇이든 이 언어로 표현할 수 있다면 흥미롭지 않은가? 지금까지 작성된 어떤 프로그램도 지금까지 배운 언어 기능만으로도 재작성할 수 있다(물론, 마우스, 디스크 같은 기기를 다루는 몇 가지 명령어는 더 배워야 하지만, 그 정도면 충분하다).

이 주장을 처음 입증한 것은 최초의 컴퓨터 과학자 중에 한 명인 앨런 튜링이 처음으로 해결한 작은 연습문제였다(앨런 튜링이 수학자였다고 주장하는 사람도 일부 있지만, 초기 컴퓨터 과학자들은 대부분 수학자로 시작했다). 이런 이유로 이 연습문제는 튜링 명제(Turing Thesis)로 알려져 있다. 튜링 명제에 대한 더 자세한(그리고 더 정확한) 설명을 원한다면 <Introduction to the Theory of Computation 3rd Ed.>(Michael Sipser, Course Technology, 2012)를 추천한다.

여러분이 지금까지 학습한 도구로 무엇을 할 수 있는지 알려주기 위해 몇 가지 수학 함수를 재귀적으로 평가해보겠다. 정의 안에 정의하고 있는 것에 대한 참조를 담고 있다는 점에서 재귀적인 정의는 환원적인 정의와 비슷하다. 그러나 진짜로 환원적인 정의는 그렇게 유용하지 않다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.