재귀호출과 피보나치 수열 탐구
재귀호출은 함수가 그 내부에서 자신을 다시 호출하는 것이다. 이는 언뜻 이상하게 보일 수 있고, 경우에 따라서는 의도치 않은 동작을 하게 할 수 있어서 일반적으로는 지양되는 방법이기는 하나, 대신에 코드가 짧아질 수 있고 실행 로직 자체가 어느 정도 제한된 경우라면 충분히 사용할 수 있다. 특히 하스켈과 같은 함수형 언어에서는 반복문을 돌리는 로직이 없기 때문에 재귀호출을 하는 함수를 자주 사용하게 된다.
피보나치 수열을 생성하는 함수를 생각해보자. 하스켈에서는 다음과 같이 함수가 정의된다.
let fibs x y = x : fibs y (y+x)
이 함수는 재귀적으로 동작한다. 첫 번째 인수를 두 번째 인수와 두 인수의 합을 인자로 넘긴 재귀호출의 결과과 연결하게 된다. 문제는 이 호출이 무한히 반복된다는 점에 있다. 2차적으로 호출되는 fibs 함수는 계속해서 자신을 호출하며, 그 끝은 없다. 보통 하스켈에서는 다음과 같은 식으로 유한한 크기의 결과를 사용한다.
> take 5 (fibs 1 2)
[1, 2, 3, 5, 8]
이러한 무한 루프를 도는 식의 계산은 다른 프로그래밍 언어에서는 연산만 하다가, 스택 오버플로우를 내고 프로그램이 뻗어버리겠지만 하스켈은 “값이 필요해지는 최종 시점”에서만 계산을 수행하게 되므로 정상적으로 동작한다. 심지어 > fibs 1 2라고만 실행해서 그 끝을 주지 않으면 해당 함수는 “다음 차의 항”이 필요할 때 계속해서 연산하며 결과를 출력해 나간다. (Ctrl+C를 눌러서 중지할 수 있다.)
이 코드를 C로 그대로 옮기기는 힘들다. (크기가 무한이 늘어날 수 있는 배열을 만들 수 없기 때문이다. 대신에 세 번째 인자로 배열의 크기를 받는다면 다음과 같이 작성할 수는 있다.
unsigned int * fibs(unsigned int x , unsigned int y, unsigned int length){
unsigned int *fib_list = malloc( length * sizeof(unsigned int));
unsigned int i=0, a = x, b = y, c;
while(i< length) {
fib_list[i] = a;
c = b;
b = a + b;
a = c;
i++;
}
return fib_list;
}
사실 위의 구현은 매우 좋지 않은데, 함수 내부에서 malloc을 써서 새로운 메모리를 할당하고 있기 때문이다. 보통 이 경우에는 아래와 같이 함수 외부에서 미리 할당하고 그 포인터를 받아 사용하도록 디자인하는 것이 좋다.
typedef unsigned int * fib_t;
void fibs(fib t, unsigned int x, unsigned int y, unsigned int length){
unsigned int i=0, r;
while(i < length) {
l[i] = x;
r = x;
x = y;
y = r+y;
i++;
}
}
파이썬의 경우, 함수형 언어의 패러다임에서 들여온 제너레이터라는 기능이 있어서 피보나치 수열은 비교적 쉽게 구현이 가능하다. (게다가 무한루프로 보이지만 안전하게 동작한다.)
def fibs(x, y):
while True:
yield x;
x, y = y, x+y
g = fibs(1, 2)
for i in range(100):
print next(g)
둘다 재귀호출을 사용하지 않고 있다. 만약 재귀호출을 사용해야 한다면 어떤 식으로 코드를 구성할까? C의 경우 계속해서 새로운 리스트를 만들어서 할당해야 하는 괴로움이 있다. 이는 연결 리스트 객체를 새롭게 정의하여 구성하는 것이 보다 깔끔한 구성이 될 수 있다. 배열을 리턴하는 함수를 작성하는 경우에는 재귀호출로 얻는 배열의 모든 원소를 뒤로 밀어내어 앞쪽에 원소를 추가하는 작업을 해야 하는데, 이것이 상당히 비싼 작업이 될 수 있다. 어떤 경우는 코드가 너무 길어질 것 같아서 패스… 하려고 했는데 맨 아래에서 다시 추가해보도록 하겠다.
파이썬으로는 재귀적으로 다음과 같이 구현할 수 있겠다.
def fibs(x, y, len):
if len == 0:
return []
else:
return [x] + fibs(y, x+y, len-1)
if __name__ == '__main__':
print fibs(1, 2, 100)
C로는 연결 리스트를 활용해서 위 파이썬 코드와 비슷한 일을 하도록 한다. 객체 지향 스타일로 연결리스트를 생성하고 값을 리스트의 맨 앞에 끼워넣는 식의 작업을 한다.
#include <stdio.h>
#include <mem.h>
typedef struct _node {
unsigned int value;
struct _node* next;
} *node;
typedef struct _list {
unsigned int length;
node head;
} *list;
list newList(){
list x = malloc(sizeof(list));
x->head = NULL;
x->length = 0;
return x;
}
void dellocList(list l){
while(l->head != NULL){
node k = l->head;
l->head = l->head->next;
free(k);
l->length--;
}
free(l);
return;
}
void addValue(list l, unsigned int a) {
node n = malloc(sizeof(node));
n->value = a;
n->next = l->head;
l->head = n;
l->length++;
}
void inspectList(list l){
int i=0;
node holder = l->head;
while(i<l->length){
printf("%d, ", holder->value);
holder = holder->next;
i++;
}
}
list fibs(list l, unsigned int x, unsigned int y, unsigned int len) {
if(len==0)
return l;
else {
addValue(fibs(l, y, x+y, len-1), x);
return l;
}
}
void convertListToArray(list l, unsigned int *k) {
int i=0;
node temp = l->head;
while(temp != NULL) {
k[i]=temp->value;
temp = temp->next;
i++;
}
}
int main(int argc, const char* argv){
list l = newList();
fibs(l, 1, 2, 20);
inspectList(l);
dellocList(l);
return 0;
}
두 종류의 객체를 사용한다. 하나는 node와 다른 하나는 list이다. list는 일종의 연결 리스트이다. 연결 리스트의 구현을 위해서는 각 노드 객체를 구현해야 하는데, 이는 _node라는 구조체의 포인터를 사용했다. node 객체의 명시적인 생성은 하지 않는 것으로 간주하고, list는 newList와 deallocList라는 두 개의 함수를 사용해서 각각 생성하고 해제한다. 또한 노드는 리스트의 처음에 값을 추가하는 addValue 함수에서 새롭게 메모리를 할당해서 저장하는데, 연결 리스트의 특성상 모든 노드들의 포인터는 순회시에 할 수 있으므로 리스트를 해제하는 시점에 내부의 모든 노드를 해제한 후 리스트를 해제하도록 했다.
끝으로 리스트를 순회하면서 정수(부호없는)의 배열로 각 노드의 값을 복사해서 연결리스트의 내용을 배열로 옮겨주는 convertListToArray() 함수를 추가했다.
(추가) 배열을 사용한 재귀호출 – C
배열을 사용한 재귀호출은 다음과 같이 구현할 수 있다. C에서 이러는 거 별로 좋아하진 않지만, 어쨌든 파이썬의 리스트로 구현하는 방식과 비슷한 구현이다.
#include <stdio.h>
#include <mem.h>
#include <string.h>
void fibs(unsigned int *l, unsigned int x, unsigned int y, unsigned int len)
{
if(len <= 1){
return;
}
else {
fibs(l, y, x+y, len-1);
memcpy(l+1, l, (len-1)*sizeof(unsigned int));
l[0] = x;
return;
}
}
int main(int argc, const char** argv){
int len = 40;
unsigned int *l = malloc(sizeof(unsigned int)*len);
fibs(l, 1, 1, len);
int i;
for(i=0;i<len;i++) {
printf("%u, ", l[i]);
}
free(l);
return 0;
}
피보나치 수열의 경우에는 좀 특수하게 앞의 두 항의 값만 있으면 그 다음 항을 계산하는 건 간단하니, 다음과 같이 객체(구조체)하나에서 다음 값을 매번 계산하도록 할 수도 있다. 파이썬의 제너레이터와는 다르지만 동작은 비슷하게 하게 된다. 이 방법이 그나마 가장 안전해보이기는 한다. (대신에 변수타입의 값 범위 내에서만 안전하다;;)
#include <stdio.h>
#include <mem.h>
typedef struct _fibgen {
unsigned int a, b, temp;
} * fibgen;
typedef void* fib_t;
fib_t newFib(void){
fibgen t = malloc(sizeof(fibgen));
t->a=1;
t->b=1;
t->temp=0;
return (fib_t)t;
}
void deallocFibgen(fib_t t) {
free(t);
}
unsigned int next(fib_t t){
fibgen f = (fibgen)t;
f->temp = f->a;
f->a = f->b;
f->b += f->a;
return f->temp;
}
int main(int argc, const char** argv){
fib_t f = newFib();
int i;
for(i=0;i<40;i++){
printf("%u, ", next(f));
}
deallocFibgen(f);
return 0;
}
