딩코딩 : Computer Science 블로그

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
} Node;

// 데이터 삽입(recursion)
void insert(struct node **root, int data) {
    struct node* ptr;
    struct node* newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    if(*root == NULL){
        *root = newNode;
        return;
    }

    ptr = *root;

    while(ptr){
        if(data < ptr->data){
            if(ptr->left == NULL){
                ptr->left = newNode;
                return;
            }
            else{
                ptr = ptr->left;
            }
        }
        else{
            if(ptr->right == NULL){
                ptr->right = newNode;
                return;
            }
            else{
                ptr = ptr->right;
            }
        }
    }
}

// 전위(preorder)탐색(recursion)
void preOrder(struct node *root) {
    if(root == NULL) return;
    printf("%d ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

// 중위(inorder)탐색(recursion)
void inOrder(struct node *root) {
    if(root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->data);
    inOrder(root->right);
}

// 후위(postorder)탐색(recursion)
void postOrder(struct node *root) {
    if(root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->data);
}

// 노드의 개수(recursion)
int size(struct node *root) {
    if(root == NULL) return 0;
    return 1 + size(root->left) + size(root->right);
}

// 높이(recursion)
int height(struct node *root) {
    if(root == NULL) return 0;
    if(root->left == NULL && root->right == NULL) return 0;

    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return 1 + (leftHeight>= rightHeight ? leftHeight : rightHeight);
}

// 미러 이미지로 변환하기(recursion)
void mirror(struct node **root) {
    if(*root == NULL) return;
    mirror(&(*root)->left);
    mirror(&(*root)->right);
    struct node *tmp = (*root)->left;
    (*root)->left = (*root)->right;
    (*root)->right = tmp;
}

// 노드에 저장된 데이터의 값의 합 구하기(recursion)
int sumOfWeight(struct node *root) {
    if(root == NULL) return 0;
    return sumOfWeight(root->left) + sumOfWeight(root->right) + root->data;
}

// 루트노드부터 단말노드까지의 경로 상의 데이터의 최대합(recusrion)
int maxPathWeight(struct node *root) {
    if(root == NULL) return 0;
    int leftWeight, rightWeight;
    leftWeight = maxPathWeight(root->left);
    rightWeight = maxPathWeight(root->right);
    return root->data + (leftWeight>=rightWeight ? leftWeight : rightWeight);
}

// 트리노드의 동적 메모리 해제하기(recursion)
void destruct(struct node **root) {
    if(*root == NULL) return;
    destruct(&((*root)->left));
    destruct(&((*root)->right));
    free(*root);
    *root = NULL;
}

재귀란

int factorial(int n){
	if (n==1) return 1
    return n * factorial(n-1);
}

재귀란 특정 함수나 개체를 설명할 때

그 함수나 개체를 바탕으로 설명하는 것을 의미한다.

특정 문제에 대해서 재귀를 이용하면 단순 반복문으로 해결하기 어려운 문제를 쉽고 간결하게 해결할 수 있다.

단 재귀를 이용해서 문제를 해결할 때는

stack Overflow가 발생하는 것을 조심해야 한다.

프로그램이 실행될 때 프로그램은

메모리에 정보를 저장하고 이용하는데 이 때 메모리의 구조는

크게 코드 영역, 데이터 영역, 힙 영역, 스택 영역으로 나뉜다.

재귀를 이용할 때 스택영역이 중요하다.

Activation Record

함수가 실행될 때 스택 영역에 activation record가 쌓인다.

activation record는 특정 함수를 실행하기 위해서 기록해두어야 하는 데이터를 의미한다.

함수 내에서 또 다른 함수를 실행하는 경우가 많다.

이러한 경우 A 함수를 실행하는 중에 B 함수가 실행 되면 다음과 같은 과정이 진행된다.

A 함수를 실행했던 데이터를 메모리의 call stack에  activation record를 기록해둔다.

B 함수의 실행이 끝나면 A 함수가 실행되던 정보를 불러오기 위해 call stack에 저장된 activation record를 불러와서

다시 A 함수를 실행할 수 있다.

즉 특정 함수를 실행할 때 그 정보를 call stack의 activation record에 기록하는 것이다.

그런데 프로그램이 사용하는 메모리는 무한한 자원이 아니다.

즉 스택 영역도 한정된 자원이다.

이 말은 함수를 재귀적으로 무한히 호출하다보면 activation record가 무한히 생성되고

이는 프로그램이 사용할 수 있는 call stack의 범위를 넘어서게 된다.

이러면 Stack Overflow 현상이 발생하는 것이다!

다만 헷갈리지 말아야할 점은 함수가 재귀적으로 무한히 실행되는 것은

activation record가 계속 쌓여서 문제가 발생하지만,

재귀적으로 실행되지 않고 일반적인 함수가 계속해서 실행되는 것은 Stack Overflow가 발생하지 않는다.

왜냐하면 함수의 실행이 끝나면 call stack에 저장된 activation record도 메모리에서 지워져서

계속 쌓이지 않기 때문이다.

그래서 base condition, 기저사례를 잘 설정해서

재귀함수를 실행하면 함수가 stack Overflow가 발생하지 않도록

잘 설계하는 것이 중요하다.

stack Overflow 발생 가능

int sum(int n){
	if (n==1) return 1
    return sum(n-1) + n;
}

위 경우 n이 엄청 커진다면 activation record가 계속 기록하여 stack overflow가 발생할 수 있다.

stack Overflow 발생 안함

while(1){
	int sum(int n, int m){
		return n + m;
	}
}

하지만 이 경우에는 함수를 실행하고 activation record를 기록하고 함수가 끝나면 바로 지우고

기록하고 지우고를 반복하여 함수는 무한히 실행하지만 실제 stack에 activation record가 무한히 쌓이는 상황은 아니다.

activation record는 몇개까지 쌓을 수 있을까?

간단한 더하기 함수를 재귀적으로 구현했을 때

함수를 4000번 정도 실행하면 Stack Overflow가 발생하는 것을 확인할 수 있었다.

이 말은 만약 재귀적으로 구현할 때 함수를 4000번 이상 실행해야 한다면 

해당 문제를 재귀적으로 해결할 수 없다는 것을 의미한다.

이때는 반복문을 이용해서 해결해야 할 것이다.

Heap Overflow?

본문과는 크게 관련없지만, 

메모리 구조에서 코드와 데이터 영역은 프로그램을 실행할 때 한번 메모리에 할당되고 크기가 변하지 않기 때문에 정적이다.

하지만 힙 영역과 스택 영역은 프로그램이 동작하는 과정에서 동적으로 이용된다.

이때 메모리가 동적으로 이용된다는 말은 프로그램이 진행하면서 계속 메모리를 일정하게 이용하는 것이 아닌,

프로그램의 진행 상황에 따라 메모리의 사용량이 변화하는 것을 의미한다.

스택을 보면 함수를 실행할 때마다 Activation Record를 기록하기 위해 메모리를 추가적으로 사용한다.

힙 영역은 프로그램 코드에서 메모리를 동적으로 할당할 때 사용된다.

주로 C, C++계열 언어에서 포인터와 new 키워드를 활용하여 힙 메모리를 할당받아 사용하는 것이 예시이다.

그렇다면 Heap Overflow도 존재하지 않을까 하는 의문이 들었다.

이에 대해 찾아보니 프로그래머가 메모리를 계속 동적으로 하고 반환해주지 않는다면

stack과 마찬가지로 heap도 overflow가 발생한다고 한다.