[C] 재귀함수를 비재귀함수로 바꾸기 2 (재귀함수 2개)[C] 재귀함수를 비재귀함수로 바꾸기 2 (재귀함수 2개)

Posted at 2015.02.19 16:00 | Posted in C



facebook에 글올리기



[C] 재귀함수를 비재귀함수로 바꾸기 2 (재귀함수 2개)


재귀함수가 2개인 재귀함수의 경우 재귀함수들과 실제 작업하는 부분의 순서에 따라 비재귀 함수로 변경하는 방법이 조금 복잡하다.


1. 실제작업하는 부분이 처음에 실행될 때


(1) 재귀 함수


 Colored By Color Scripter

// 전위 표기법
void preorder_traverse(node *t){
    if (t != tail){
        visit(t);               // 실제 작업하는 부분
        preorder_traverse(t->left);    // 재귀 1
        preorder_traverse(t->right);  // 재귀 2
    }
}


(2) 비재귀 함수


 Colored By Color Scripter

// 전위 표기법 비재귀 함수
void non_recursive_preorder_traverse(node *t){
    
    push(t);
    while (!is_stack_empty()){
        t = pop();
        if (t != tail){
            visit(t);                  // 실제 작업하는 부분
            push(t->right);        // 재귀 2  인자 스택이기에 나중에 수행할 right를 먼저 넣는다.
            push(t->left);         // 재귀 1  인자
        }
    }
}



2. 실제 작업하는 부분이 중간에 위치할 때


(1) 재귀 함수


 Colored By Color Scripter

// 중위 표기법
void inorder_traverse(node *t){
    if (t != tail){
        inorder_traverse(t->left);     // 재귀 1
        visit(t);                                // 실제 작업하는 부분
        inorder_traverse(t->right);  // 재귀 2
    }
}



(2) 비재귀 함수


 Colored By Color Scripter

// 중위 표기법을 비재귀 함수로
void non_recursive_inorder_traverse(node *t){
    while (1){
        while (t != tail){
            push(t);             // 재귀 1 스택에 push
            t = t->left;
        }
        if (!is_stack_empty()){
            t = pop();
            visit(t);               // 실제 작업하는 부분
            t = t->right;       // 재귀 2   인자 변경
        }
        else{
            break;
        }
    }
}




3. 실제 작업하는 부분이 마지막에 위치할 때


(1) 재귀 함수


Colored By Color Scripter

// 후위 표기법
void postorder_traverse(node *t){
    if (t != tail){
        postorder_traverse(t->left);       // 재귀 1
        postorder_traverse(t->right);    // 재귀 2
        visit(t);                                     // 실제 작업하는 부분
    }
}


(2) 비재귀 함수


Colored By Color Scripter

// 후위표기법 비재귀 함수로 변환
void non_recursive_postorder_traverse(node *t){
    int done = 0;
    node *s;    // 인자 리스트의 복사본

    while (!done){
        while (t != tail){    // 인자리스트 푸쉬
            push(t);
            t = t->left;             //  재귀 1 인자리스트 푸쉬
        }
        while (!is_stack_empty()){
            s = t;        // 인자리스트 복사
            t = pop();
            if (t->right != tail){
                if (t->right == s){
                    visit(t);           // 실제 작업하는 부분
                }
                else{
                    push(t);
                    t = t->right;       // 재귀 2 인자리스트
                    break;
                }
            }
            else{
                visit(t);            // 실제 작업하는 부분
            }
            if (is_stack_empty()){
                done = 1;
            }
        }
    }
}


저작자 표시 비영리 변경 금지
신고
이웃추가
facebook에 글올리기

Name __

Password __

Link (Your Website)

Comment

SECRET | 비밀글로 남기기