스택(not done)

함수는 단순히 코드로만 이뤄지지 않는다. 함수가 다른 함수를 호출하거나 함수가 자기 자신을 호출하는 경우도 자주 있다.

이런 경우를 재귀(recursion)이라고 한다. 그리고 재귀는 아주 쓸모가 많다.

예제를 하나 살펴보자. 여러분의 핸드폰은 아마도 JPEG압축을 사용해 사진 크기를 감소시킬 것이다. 이미지 압축이 어떻게 작용하는지 보기 위해 아래 정사각형 흑백 이미지를 살펴보자.

재귀적 분할(recursive subdivision)을 사용해 압축을 해보자. 이미지를 보면 모든 픽셀이 똑같은 색이 아니다. 이를 네 부분으로 나누고, 각 부분을 검사한다. 이 과정을 1픽셀짜리 조각이 생길 때까지 계속한다. 이 함수를 보면,

function subdivide(x, y, size) {
    if (size = !1 && 정사각형 안의 픽셀이 모두 같은 색이 아님 )
    {
        half = size / 2
        subdivide(x, y, half) // 왼쪽 아래 사분면을 분할
        subdivide(x, y + half, half) // 왼쪽 위 사분면을 분할
        subdivide(x + half, y + half, half) // 오른쪽 위 사분면을 분할
        subdivide(x + half, y, half) // 오른쪽 아래 사분면을 분할
    }
    else
    {
        정사각형에 대한 정보를 저장
    }
}

subdivide 함수는 왼쪽 아래 사분면, 왼쪽 위, 오른쪽 위, 오른쪽 아래 순서로 이미지를 색이 똑같은 정사각형 덩어리로 나눈다. 위 그림은 앞에서 본 웃는 얼굴을 subdivide 함수를 사용해 그리는 방법을 표현한 그림이다. 분할이 필요한 경우는 회색, 모든 색이 같은 경우는 흰색이나 검은색으로 표시했다.

이 그림에 있는(추상적) 구조는 컴퓨터매니아들이 트리(나무)라고 부르고 수학에서 유향비 순환 그래프(DAG- directed acyclic graph)라고 부르는 구조다. 이 구조는 화살표를 따라가면서 읽는다. 이 구조에서 화살표는 더 위쪽을 가리킬 수 없기 때문에 순환(cycle 또는 loop)이 없다. 화살표가 뻗어나가지 않는 부분을 잎 노드(leaf node)라고 부르며, 나뭇가지의 맨 끝에 잎이 달려 있는 것처럼 잎 노드도 트리의 맨 마지막에 달려 있다. 여러분이 눈에 힘을 주고 세어보면 위 그림에 회색이 아닌 사각형이 40개 있음을 알 수 있다. 이 수는 원래 이미지의 픽셀 수인 64개와 비교하면 훨씬 작은 수로, 이 말은 저장해야 할 정보가 줄어든다는 뜻이다. 이것이 바로 압축이다.

몇 가지 이유로 인해, 그리고 그리기 쉽다는 이유로 인해(또는 컴퓨터 매니아들이 밖에 나가 실제 나무를 본 적이 별로 없기 때문에) 컴퓨터 매니아들은 항상 트리의 뿌리(root -루트)를 맨 위에 놓고 트리를 아래쪽으로 자라나게 그린다. 그림 5-4에 있는 트리는 각 노드에서 가지가 4개 뻗어나가기 때문에 쿼드트리(quad tree) 부른다. 쿼드트리는 공간 데이터 구조(spatial data structure)에 속한다 하난 사멧(Hanan Samet)은 이 주제(쿼드트리와 공간 데이터 구조)를 평생 공부했으며, 이 주제를 다룬 멋진 책을 몇 권 썼다.

앞 절에서 본 방법으로 subdivide 함수를 구현하면 문제가 생긴다. 반환값을 저장할 위치가 한 군데뿐이기 때문에 subdivide 같이 재귀적인 함수는 이미 들어 있던 반환값을 덮어써서 되돌아 갈 위치를 잃어버리기 때문에 자기 자신을 호출할 수가 없다.

일단 여기까지