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

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

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

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

(1) 재귀 함수

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

(2) 비재귀 함수

// 전위 표기법 비재귀 함수 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) 재귀 함수

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

(2) 비재귀 함수

// 중위 표기법을 비재귀 함수로 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) 재귀 함수

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

(2) 비재귀 함수

// 후위표기법 비재귀 함수로 변환 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;             }         }     } }

출처: https://hyeonstorage.tistory.com/353?category=622873 [개발이 하고 싶어요]