결과가 있는 함수

[fruitchap]

반환값

우리가 사용한 내장함수들 중 몇몇은, 수학 함수 같은 것들, 결과를 만듭니다. 함수 호출은 값을 만들고, 우리는 보통 변수에 대입하거나 표현식의 일부로 사용합니다.

e = math.exp(1.0)
height = radius * math.sin(radians)

지금까지 우리가 작성한 모든 함수는 결과가 없습니다; 뭔가를 인쇄하거나 거북이를 이리저리 움직입니다만 반환값은 None 입니다.

이 장에서는, (마침내) 결과가 있는 함수를 쓰려고 합니다. 첫째 예는 area인데, 주어진 반경을 갖는 원의 면적을 돌려줍니다:

def area(radius):
    temp = math.pi * radius**2
    return temp

우리는 앞에서 return 문장을 봤습니다만, 결과가 있는 함수에서는 return 문이 표현식을 포함합니다. 이 문장은 이런 뜻입니다: “이 함수로부터 즉시 복귀하고, 표현식을 반환값으로 사용하라.” 표현식은 얼마든지 복잡해질 수 있기 때문에, 이 함수를 좀 더 간결하게 쓸 수도 있습니다:

def area(radius):
    return math.pi * radius**2

반면에, temp 와 같은 임시 변수는 종종 디버깅을 수월하게 만듭니다.

때로 여러 개의 return 문을 쓰는 것이 유용합니다, 조건문의 분기당 하나씩:

def absolute_value(x):
    if x < 0:
        return -x
    else:
        return x

이 return 문들은 대안적인 조건문에 들어있기 때문에, 단지 어느 하나만이 실행됩니다.

return 문이 실행되자마자, 함수는 남은 문장들의 실행 없이 종료합니다. return 문의 뒤나 실행 흐름이 결코 도달할 수 없는 그 외의 장소에 등장하는 코드들은 죽은 코드라고 불립니다.

결과가 있는 함수에서, 프로그램의 모든 가능한 경로가 return 문에 도달하도록 만드는 것은 좋은 생각입니다. 예를 들어:

def absolute_value(x):
    if x < 0:
        return -x
    if x > 0:
        return x

이 함수는 올바르지 않은데, 만약 x 가 0이 될 경우, 어느 조건도 참이 아니고, 함수는 return 문을 만나지 못하고 종료하기 때문입니다. 만약 실행 흐름이 함수의 끝에 도달한다면, 반환값은 None 이 되고, 이는 0 의 절대값(absolute value)이 아닙니다.

>>> print absolute_value(0)
None

말이 나온 김에 이야기하자면, 파이썬은 절대값을 계산하는 내장함수 abs를 제공합니다.

[연습 6.1.]

x > y 면 1을, x == y 면 0을, x < y 면 -1을 돌려주는 compare 함수를 작성하세요.

점진적 개발

[incremental.development]

커다란 함수를 작성할 때, 아마도 여러분이 디버깅에 더 많은 시간을 들이고 있음을 발견하게 될 것입니다.

점점 복잡해지는 프로그램을 다루기 위해, 여러분은 소위 점진적 개발이라고 불리는 과정을 시도하길 원할 수 있습니다. 점진적 개발의 목표는, 단지 한번에 소량의 코드만을 추가하고 검사함으로써, 긴 디버깅 활동을 회피하는 것입니다.

예를 들어, 좌표 \((x_1, y_1)\) 와 \((x_2, y_2)\) 인 두 점간의 거리를 찾길 원한다고 가정하세요. 피타고라스의 정리에 따라, 거리는 이렇습니다:

\[\mathrm{distance} = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\]

첫 단계는 distance 함수가 파이썬으로 어떤 모습이어야 하는지 생각해보는 것입니다. 다른 말로 하면, 입력 (매개변수)은 무엇이고, 출력 (반환값)은 무엇인가요?

이 경우에, 입력은 두 점이고, 네 개의 숫자를 사용해서 표현할 수 있습니다. 반환값은 거리인데, 실수 값입니다.

이미 여러분은 함수의 윤곽을 쓸 수 있습니다:

def distance(x1, y1, x2, y2):
    return 0.0

명백하게, 이 버전은 거리를 계산하지 않습니다; 항상 0을 돌려줍니다. 하지만 문법적으로 옳고, 실행되는데, 더 복잡하게 만들기 전에 검사할 수 있다는 것을 뜻합니다.

새 함수를 검사하려면, 간단한 인자로 호출하세요:

>>> distance(1, 2, 4, 6)
0.0

저는 이 값을 선택함에 있어, 수평거리가 3이고, 수직거리가 4가 되도록 했습니다; 그렇게 하면 결과는 5 (3-4-5 삼각형의 빗변) 입니다. 함수를 검사할 때, 올바른 답을 알고 있는 것은 유용합니다.

이 지점에서, 우리는 함수가 문법적으로 올바르다는 것을 확인했고, 바디에 코드를 추가할 수 있습니다. 합리적인 다음 단계는 차 \(x_2 - x_1\) 와 \(y_2 - y_1\) 를 구하는 것입니다. 다음 버전은 그 값들을 임시 변수에 저장하고 인쇄합니다.

def distance(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1
    print 'dx is', dx
    print 'dy is', dy
    return 0.0

만약 함수가 동작한다면, 'dx is 3' 과 'dy is 4' 를 출력합니다. 만약 그렇다면, 우리는 함수가 올바른 인자를 받고 있고, 첫 번째 계산을 올바르게 수행한다는 것을 알게 됩니다. 그렇지 않다면, 검사해야 할 것은 단지 몇 줄에 지나지 않습니다.

다음으로 우리는 dx 와 dy 의 제곱의 합을 계산합니다:

def distance(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1
    dsquared = dx**2 + dy**2
    print 'dsquared is: ', dsquared
    return 0.0

다시 한번, 여러분은 이 단계에서 프로그램을 실행하고 출력을 검사합니다(25가 맞습니다). 마지막으로, 계산하는데 math.sqrt 를 사용할 수 있고, 결과를 돌려줍니다:

def distance(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1
    dsquared = dx**2 + dy**2
    result = math.sqrt(dsquared)
    return result

올바르게 동작한다면 완성한 것입니다. 그렇지 않다면, return 문 전에, result 의 값을 인쇄하고 싶을 겁니다.

함수의 최종 버전은 실행할 때 아무 것도 출력하지 않습니다; 단지 값을 돌려주기만 합니다. 우리가 쓴 print 문장들은 디버깅에 유용합니다만, 일단 함수가 동작하면 제거해야 합니다. 이런 코드들을 비계(scaffolding)라고 부르는데, 프로그램을 쌓아 올리는 데는 유용하지만, 최종 제품의 일부는 아니기 때문입니다.

여러분이 시작할 때는 한번에 한두 줄만을 추가해야 합니다. 여러분이 경험을 쌓음에 따라, 더 큰 묶음을 쓰고 디버깅하고 있는 여러분을 발견하게 될 것입니다. 어느 쪽이든, 점진적 개발은 여러분의 디버깅 시간을 많이 줄여줄 수 있습니다.

이 과정의 핵심 요소들은 이렇습니다:

동작하는 프로그램으로 시작해서 작고 점진적인 변경을 만드세요. 아무 때나, 만약 오류가 있다면, 여러분은 어디에서 발생했는지 쉽게 알 수 있습니다.
출력하고 검사하기 위해, 임시 변수에 중간 값들을 저장하세요.
일단 프로그램이 동작하면, 비계들을 제거하거나, 여러 개의 문장을 하나의 복합적인 표현식으로 합치고 싶을 수 있습니다만, 프로그램을 더 읽기 어렵게 만들지 않을 때만 그렇게 하세요.

[연습 6.2.]

점진적 개발을 사용해서, 두 변의 길이가 주어진 직각 삼각형의 빗변의 길이를 돌려주는 함수 hypotenuse 를 작성하세요. 작업하면서 각 개발 단계를 기록하세요.

합성

지금쯤은 여러분이 기대하고 있을법한데, 한 함수 안에서 다른 함수를 호출할 수 있습니다. 이 능력을 합성이라고 부릅니다.

예로, 두 점,원의 중심과 원주상의 한 점,을 받아들여서 원의 면적을 계산하는 함수를 작성할 것입니다.

중심은 변수 xc 와 yc 에 저장되고, 원주상의 점은 xp 와 yp 에 저장된다고 가정하세요. 첫 단계는 원의 반경을 구하는 것인데, 두 점간의 거리입니다. 방금 전에 distance 라는 함수를 썼는데, 바로 그 일을 합니다:

radius = distance(xc, yc, xp, yp)

다음 단계는 그 반경을 사용해서 원의 면적을 구하는 것입니다; 이 역시 방금 전에 작성했습니다:

result = area(radius)

이러한 단계들을 함수로 캡슐화하면 이렇게 됩니다:

def circle_area(xc, yc, xp, yp):
    radius = distance(xc, yc, xp, yp)
    result = area(radius)
    return result

임시 변수 radius 와 result 는 개발과 디버깅에 유용합니다만, 일단 프로그램이 동작하면, 함수 호출을 조합함으로써 더 간결하게 만들 수 있습니다.

def circle_area(xc, yc, xp, yp):
    return area(distance(xc, yc, xp, yp))

논리 함수

[boolean]

함수는 논리값을 돌려줄 수 있는데, 종종 복잡한 검사를 함수 안에 숨기는 용도로 편리합니다. 예를 들어:

def is_divisible(x, y):
    if x % y == 0:
        return True
    else:
        return False

논리 함수의 이름을 예/아니오를 묻는 질문처럼 들리도록 만드는 것이 일반적입니다; is_divisible 는 x 가 y 로 나누어 떨어지는지 여부를 True 나 False 로 돌려줍니다.

여기 예가 있습니다:

>>>   is_divisible(6, 4)
False
>>>   is_divisible(6, 3)
True

== 연산자의 결과는 논리값이기 때문에, 바로 돌려줌으로써 함수를 더 간결하게 쓸 수 있습니다:

def is_divisible(x, y):
    return x % y == 0

논리 함수는 종종 조건문에 사용됩니다:

if is_divisible(x, y):
    print 'x is divisible by y'

이런 것을 쓰고 싶을 수 있습니다:

if is_divisible(x, y) == True:
    print 'x is divisible by y'

하지만 추가의 비교는 필요하지 않습니다.

[연습 6.3.]

\(x \le y \le z\) 면 True를, 그렇지 않으면 False를 돌려주는 함수 is_between(x, y, z)를 작성하세요.

재귀 다시 보기

[more.recursion]

우리는 파이썬의 작은 부분집합만을 다뤘습니다만, 아마 여러분은 이 부분집합이 완전한 프로그래밍 언어라는 것에 관심 있을 수 있는데, 모든 것이 이 언어로 계산되거나 표현될 수 있다는 것을 뜻합니다. 작성된 어떤 프로그램도 단지 여러분이 지금까지 배운 언어 기능만으로 다시 쓸 수 있습니다(사실 키보드, 마우스, 디스크등의 장치들을 제어하기 위한 몇 개의 명령들이 더 필요할 것입니다만, 그게 전부 입니다).

이 주장의 증명은 자명하지 않은 작업인데, 최초의 컴퓨터 과학자중 하나인 앨런 튜링(Alan Turing)에 의해 이루어졌습니다(어떤 사람들은 그가 수학자였다고 지적하지만, 많은 초기의 컴퓨터 과학자들은 수학자로 시작했습니다). 이런 연유로, 튜링 명제(Turing Thesis)라고 알려져 있습니다. 튜링 명제에 대한 좀 더 완전한 (그리고 정확한) 토론으로, Michael Sipser 의 책 Introduction to the Theory of Computation 을 추천합니다.

지금까지 배운 도구들로 무엇을 할 수 있는지에 대한 아이디어를 주기 위해, 재귀적으로 정의된 수학함수 몇 개를 다루겠습니다. 재귀적 정의는 순환적인 정의와 유사한데, 정의가 정의되는 것에 대한 참조를 내포한다는 점에서 그렇습니다. 진짜로 순환적인 정의는 그리 유용하지 않습니다:

보팔(vorpal):: 보팔한 것을 묘사하는데 사용되는 형용사.

만약 이런 정의를 사전에서 보게 된다면 짜증스러울 겁니다. 반면에, \(!\) 기호로 표시되는 팩토리얼(factorial)의 정의를 찾아보면, 이런 것을 찾게 됩니다:

\[\begin{split}\begin{aligned} && 0! = 1 \\ && n! = n (n-1)!\end{aligned}\end{split}\]

이 정의는 0 의 팩토리얼은 1 이고, 그 외의 모든 다른 값, \(n\), 의 팩토리얼은 \(n\) 에 \(n-1\) 의 팩토리얼을 곱한 것이라고 합니다.

그래서 \(3!\) 은 3 곱하기 \(2!\) 인데, \(2!\) 는 2 곱하기 \(1!\) 이고, \(1!\) 은 1 곱하기 \(0!\) 입니다. 다 합치면, \(3!\) 은 3 곱하기 2 곱하기 1 곱하기 1 으로 6이 됩니다.

여러분이 어떤 것에 대한 재귀적 정의를 쓸 수 있다면, 보통 그 것을 계산할 수 있는 파이썬 프로그램을 작성할 수 있습니다. 첫 단계는 매개변수가 무엇인지 정하는 것입니다. 이 경우에 factorial 이 정수를 받아들여야 함은 명백합니다:

def factorial(n):

만약 인자가 0 이면, 우리가 할 일은 단지 1을 돌려주는 것입니다:

def factorial(n):
    if n == 0:
        return 1

그렇지 않으면, 그리고 이 것이 흥미로운 부분인데, 우리는 \(n-1\) 의 팩토리얼을 구해서 \(n\) 을 곱하기 위해 재귀적 호출을 사용합니다:

def factorial(n):
    if n == 0:
        return 1
    else:
        recurse = factorial(n-1)
        result = n * recurse
        return result

이 프로그램의 실행 흐름은 [recursion] 절에서 나온 countdown 의 흐름과 비슷합니다. factorial 를 3으로 호출하면:

3은 0이 아니기 때문에, 두 번째 분기를 취해서 n-1의 팩토리얼을 계산한다...

2는 0이 아니기 때문에, 두 번째 분기를 취해서 n-1의 팩토리얼을 계산한다...

1은 0이 아니기 때문에, 두 번째 분기를 취해서 n-1의 팩토리얼을 계산한다...

0은 0 이기 때문에, 첫 번째 분기를 취해서 더 이상의 재귀적 호출 없이 1을 돌려준다.

반환값 (1) 에 \(n\), 값은 1,을 곱해서 그 결과를 돌려준다.

반환값 (1) 에 \(n\), 값은 2,을 곱해서 그 결과를 돌려준다.

반환값 (2) 에 \(n\), 값은 3,을 곱해서 나온 결과, 6,는 전 과정을 시작한 함수 호출의 반환값이 된다.

그림 [fig.stack3] 은 이런 일련의 함수 호출에서 스택 다이어그램이 어떻게 보이는지 보여줍니다.

[fig.stack3]

반환값은 스택을 거슬러 올라가며 전달되는 것으로 보여집니다. 각 프레임에서, 반환값은 result 의 값인데, n 에 recurse 를 곱한 것입니다.

마지막 프레임에서, 지역 변수 recurse 와 result 는 존재하지 않는데, 그들을 만드는 분기가 실행되지 않기 때문입니다.

믿음의 도약

실행의 흐름을 따르는 것은 프로그램을 읽는 한가지 방법입니다만, 금방 미궁에 빠지게 됩니다. 대안은 제가 “믿음의 도약”이라고 부르는 것입니다. 함수 호출을 만나면, 실행의 흐름을 따르는 대신, 함수가 올바로 동작하고 정확한 결과를 돌려준다고 가정하는 것입니다.

사실, 여러분은 이미 내장 함수를 사용할 때 믿음의 도약을 연습하고 있습니다. math.cos 와 math.exp 를 호출할 때, 여러분은 이 함수들의 바디를 확인하지 않습니다. 여러분은 내장 함수를 쓴 사람이 훌륭한 프로그래머이기 때문에 함수들이 동작할 것이라고 가정하기만 합니다.

여러분이 여러분 자신의 함수들을 호출할 때도 마찬가지입니다. 예를 들어, [boolean] 절에서, 한 숫자가 다른 숫자로 나누어 떨어지는지 판단하는 is_divisible 라는 함수를 작성했습니다. 일단 우리가 이 함수가 올바르다고 우리 자신을 설득하면—코드 확인과 검사를 통해—다시 바디를 보는일 없이 함수를 사용할 수 있습니다.

재귀적 프로그램도 마찬가지 입니다. 재귀적 호출과 만날 때, 실행 흐름을 따르는 대신, 재귀적 호출이 작동한다고 가정 하고 (올바른 결과를 줍니다), 여러분 자신에게 물어야 합니다, “\(n-1\) 의 팩토리얼을 구할 수 있다고 가정할 때, \(n\) 의 팩토리얼을 계산할 수 있을까?” 이 경우에, 여러분이 할 수 있다는 것은 명백합니다, \(n\) 을 곱하면 되지요.

물론, 아직 완성하지 못한 함수를 작동한다고 가정하는 것은 좀 이상합니다만, 그 것이 믿음의 도약이라고 불리는 이유입니다!

예제 하나 더

[one.more.example]

다음으로, 재귀적으로 정의된 수학 함수의 가장 널리 알려진 예는 피보나치(fibonacci) 인데, 다음과 같이 정의되어 있습니다(http://en.wikipedia.org/wiki/Fibonacci_number 를 보세요):

\[\begin{split}\begin{aligned} && \mathrm{fibonacci}(0) = 0 \\ && \mathrm{fibonacci}(1) = 1 \\ && \mathrm{fibonacci}(n) = \mathrm{fibonacci}(n-1) + \mathrm{fibonacci}(n-2)\end{aligned}\end{split}\]

파이썬으로 번역하면 이렇게 됩니다:

def fibonacci (n):
    if n == 0:
        return 0
    elif  n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

여기서 실행의 흐름을 따르려고 하면, 비교적 작은 \(n\) 에서 조차, 여러분의 머리는 터지고 말 것입니다. 그러나 믿음의 도약에 따라, 여러분이 두 개의 재귀적 호출이 올바르게 동작한다고 가정한다면, 두 값을 함께 더함으로써 올바를 결과를 얻을 수 있음은 명백해집니다.

형 검사

[guardian]

우리가 factorial을 호출할 때 인자로 1.5를 준다면 어떻게 될까요?

>>> factorial(1.5)
RuntimeError: Maximum recursion depth exceeded

무한 재귀처럼 보입니다. 그러나 어떻게 그럴 수가 있을까요? 기저 사례가 있습니다—n == 0일 때. 하지만 만약 n이 정수가 아니라면, 기저 사례를 놓치고 영원히 재귀할 수 있습니다.

첫째 재귀적 호출에서 n의 값은 0.5입니다. 다음에는, -0.5 입니다. 거기서부터, 점점 작아지지만(더 큰 음수), 결코 0 이 되지는 않습니다.

두 가지 선택이 있습니다. factorial 함수가 실수로도 동작하도록 일반화하려고 시도할 수 있습니다. 또는 factorial 이 인자의 형을 검사하도록 만들 수 있습니다. 첫 번째 옵션은 감마 함수(gamma function)라고 불리고, 이 책의 범위를 약간 벗어납니다. 그래서 우리는 두 번째로 가겠습니다.

형을 확인하려면 isinstance 함수를 사용할 수 있습니다. 거기서 인자가 양수인지도 확인할 수 있습니다.

def factorial (n):
    if not isinstance(n, int):
        print '팩토리얼은 정수에 대해서만 정의됩니다.'
        return None
    elif n < 0:
        print '팩토리얼은 음의 정수에 대해 정의되지 않습니다.'
        return None
    elif n == 0:
        return 1
    else:
        return n * factorial(n-1)

첫 번째 기저사례는 정수가 아인 경우를 다룹니다; 두 번째는 음의 정수를 잡아냅니다. 두 경우 모두, 프로그램은 뭔가 잘못되었음을 알리기 위해 오류 메시지를 인쇄하고 None을 돌려줍니다:

>>> factorial('fred')
팩토리얼은 정수에 대해서만 정의됩니다.
None
>>> factorial(-2)
팩토리얼은 음의 정수에 대해 정의되지 않습니다.
None

두 개의 검사를 통과하면, \(n\) 이 양수이거나 0임을 알게 되고, 재귀가 종료함을 증명할 수 있습니다.

이 프로그램은 때로 파수꾼(guardian)이라고 불리는 패턴을 예시합니다. 처음 두 개의 조건은 뒤따라오는 코드를 오류를 일으키는 값들로부터 보호하는 파수꾼 역할을 합니다. 파수꾼은 코드의 올바름을 증명할 수 있도록 합니다.

[raise] 절에서 오류 메시지를 인쇄하는 것보다 좀더 유연한 대안을 보게 됩니다: 예외를 일으키는 것입니다.

디버깅

[factdebug]

큰 프로그램을 더 작은 함수들로 쪼개는 것은, 디버깅의 측면에서 자연스러운 검사 점들을 만들어냅니다. 함수가 동작하지 않으면, 세 가지 가능성을 고려해볼 수 있습니다:

함수가 받아들이는 인자가 잘못되었습니다; 사전조건을 위반했습니다.
함수에 뭔가 잘못된 것이 있습니다; 사후조건을 위반했습니다.
반환값이나 그 것이 사용되는 방법에 뭔가 잘못된 것이 있습니다.

첫 번째 가능성을 제거하려면, print 문을 함수의 첫머리에 넣어 매개변수 (와 아마도 그들의 형)의 값을 인쇄할 수 있습니다. 또는 사전조건을 구체적으로 검사하는 코드를 작성할 수 있습니다.

매개변수에 문제가 없어 보이면, 각 return 문 앞에 반환값을 인쇄하는 print 문을 추가하세요. 가능하다면, 결과를 손으로 확인하세요. 결과를 확인하기 쉬운 값으로 함수를 호출하는 것을 고려하세요([incremental.development] 절에서처럼).

함수가 동작하는 것처럼 보인다면, 함수 호출을 살펴서 반환값이 올바르게 사용되고 있는지 (또는 사용되고 있기는 한지!) 확실히 하세요.

함수의 처음과 끝에 인쇄문을 넣는 것은 실행의 흐름을 좀더 가시적으로 만드는데 도움을 줍니다. 예를 들어, 여기 인쇄문을 넣은 factorial 버전이 있습니다:

def factorial(n):
    space = ' ' * (4 * n)
    print space, 'factorial', n
    if n == 0:
        print space, 'returning 1'
        return 1
    else:
        recurse = factorial(n-1)
        result = n * recurse
        print space, 'returning', result
        return result

space 는 출력의 들여쓰기를 제어하기 위한 공백 문자의 문자열입니다. 여기 factorial(5) 의 결과가 있습니다:

                    factorial 5
                factorial 4
            factorial 3
        factorial 2
    factorial 1
factorial 0
returning 1
    returning 1
        returning 2
            returning 6
                returning 24
                    returning 120

실행 흐름이 혼란스럽다면, 이런 종류의 출력은 도움이 될 수 있습니다. 효과적인 비계를 개발하는 데는 시간이 들어갑니다만, 약간의 비계는 많은 디버깅을 절약할 수 있습니다.

용어

임시 변수 temporary variable:: 복잡한 계산에서 중간 값을 저장하는데 사용되는 변수.
죽은 코드 dead code:: 프로그램에서 실행될 수 없는 부분을 뜻하며, 종종 return 문 뒤에 나오기 때문이다.
None:: return 문이 없거나 인자가 없는 return 문을 갖는 함수가 돌려주는 특별한 값.
점진적 개발 incremental development:: 한번에 작은 분량의 코드만을 추가하고 검사함으로써 디버깅을 회피하려는 프로그램 개발 계획.
비계 scaffolding:: 프로그램 개발 도중에 사용되지만 최종 버전에는 포함되지 않는 코드.
파수꾼 guardian:: 오류를 일으킬 수 있는 상황을 검사하고 처리하기 위해 조건문을 사용하는 프로그래밍 패턴.

연습

[연습 6.4.]

다음 프로그램의 스택 다이어그램을 그리세요. 프로그램은 무엇을 인쇄합니까? 답: http://thinkpython.com/code/stack_diagram.py.

def b(z):
    prod = a(z, z)
    print z, prod
    return prod

def a(x, y):
    x = x + 1
    return x * y

def c(x, y, z):
    total = x + y + z
    square = b(total)**2
    return square

x = 1
y = x + 1
print c(x, y+3, x+y)

[연습 6.5.] [ackermann]

애커만 함수(Ackermann function), \(A(m, n)\), 는 이렇게 정의됩니다:

\[\begin{split}\begin{aligned} A(m, n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases} \end{aligned}\end{split}\]

http://en.wikipedia.org/wiki/Ackermann_function를 보세요. 애커만 함수를 계산하는 함수 ack를 작성하세요. 함수를 사용해서 ack(3, 4)를 계산하세요. 결과는 125가 되어야 합니다. m 과 n에 더 큰 값을 사용하면 어떻게 됩니까? 답: http://thinkpython.com/code/ackermann.py.

[연습 6.6.] [palindrome]

회문(palindrome)은 “noon” 과 “redivider” 처럼 앞뒤 어느 쪽으로도 철자가 같은 단어입니다. 재귀적으로, 어떤 단어의 처음과 마지막 글자가 같고, 가운데가 회문 이면 그 단어는 회문 입니다.

다음은 문자열 인자를 받아들여, 처음, 끝, 가운데 글자들을 돌려주는 함수들입니다:

def first(word):
    return word[0]

def last(word):
    return word[-1]

def middle(word):
    return word[1:-1]

어떻게 이 것들이 동작하는지는 [strings]장에서 다룰 것입니다.

이 함수들을 palindrome.py 라는 이름의 파일에 입력하고 실험해 보세요. 두 글자 짜리 문자열로 middle 을 호출하면 어떻게 되나요? 한 글자는? '' 처럼 쓰고 글자를 포함하지 않는 빈 문자열은 어떻게 되나요?
문자열을 받아서 회문이면 True를, 그렇지 않으면 False를 돌려주는 함수 is_palindrome 를 작성하세요. 문자열의 길이를 검사하는데 내장 함수 len을 사용할 수 있음을 기억하세요.

답: http://thinkpython.com/code/palindrome_soln.py.

[연습 6.7.]

숫자, \(a\), 가 \(b\) 로 나누어 떨어지고, \(a/b\) 가 \(b\) 의 거듭제곱이면, \(a\) 는 \(b\) 의 거듭제곱입니다. 매개변수 a 와 b를 받아들이고, a 가 b 의 거듭제곱이면 True를 돌려주는 함수 is_power를 작성하세요. 노트: 기저 사례에 대해 생각해야 합니다.

[연습 6.8.]

\(a\) 와 \(b\) 의 최대공약수 (GCD) 는 두 숫자를 모두 나머지 없이 나눌 수 있는 가장 큰 수 입니다.

두 숫자의 GCD 를 찾는 한가지 방법은 오일러의 알고리즘인데, \(a\) 를 \(b\) 로 나눴을 때의 나머지 \(r\) 에 대해 \(gcd(a, b) = gcd(b, r)\) 가 성립한다는 관찰에 기반합니다. 기저 사례로, \(gcd(a, 0) = a\) 를 사용할 수 있습니다.

매개변수 a 와 b를 받아서 그들의 최대공약수를 돌려주는 함수 gcd를 작성하세요. 도움이 필요하면, http://en.wikipedia.org/wiki/Euclidean_algorithm를 보세요.

출처: 이 연습은 Abelson 과 Sussman의 Structure and Interpretation of Computer Programs에 있는 연습에 기반합니다.