간단한 문제를 해결하기 위해 수년간의 프로그래밍에서 재귀를 많이 사용했지만 때로는 메모리 / 속도 문제로 인해 반복이 필요하다는 것을 완전히 알고 있습니다.
그래서 언젠가는 과거에 반복에 대한 일반적인 재귀 접근 방식을 변형시키는 “패턴”또는 교과서 방식이 존재하는지 찾아서 아무것도 찾지 못했습니다. 또는 적어도 내가 기억할 수있는 것은 도움이되지 않습니다.
- 일반적인 규칙이 있습니까?
- “패턴”이 있습니까?
답변
일반적으로 재귀 함수에 일반적으로 전달되는 매개 변수를 스택으로 푸시하여 재귀 알고리즘을 반복 알고리즘으로 바꿉니다. 실제로, 프로그램 스택을 자신의 것으로 교체하고 있습니다.
Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
// Do something
my_object = stack.pop();
// Push other objects on the stack.
}
참고 : 내부에 둘 이상의 재귀 호출이 있고 호출 순서를 유지하려면 스택에 역순으로 호출을 추가해야합니다.
foo(first);
foo(second);
에 의해 대체되어야한다
stack.push(second);
stack.push(first);
편집 : 기사 스택 및 재귀 제거 (또는 기사 백업 링크 )는이 주제에 대해 자세히 설명합니다.
답변
실제로 가장 일반적인 방법은 자신의 스택을 유지하는 것입니다. C의 재귀 퀵 정렬 기능은 다음과 같습니다.
void quicksort(int* array, int left, int right)
{
if(left >= right)
return;
int index = partition(array, left, right);
quicksort(array, left, index - 1);
quicksort(array, index + 1, right);
}
자체 스택을 유지하여 반복적으로 만드는 방법은 다음과 같습니다.
void quicksort(int *array, int left, int right)
{
int stack[1024];
int i=0;
stack[i++] = left;
stack[i++] = right;
while (i > 0)
{
right = stack[--i];
left = stack[--i];
if (left >= right)
continue;
int index = partition(array, left, right);
stack[i++] = left;
stack[i++] = index - 1;
stack[i++] = index + 1;
stack[i++] = right;
}
}
분명히이 예제는 스택 경계를 확인하지 않습니다 … 실제로 왼쪽과 오른쪽 값이 주어진 최악의 경우를 기준으로 스택의 크기를 조정할 수 있습니다. 그러나 당신은 아이디어를 얻습니다.
답변
재귀 함수가 본문에서 두 번 이상 자신을 호출하는 곳을 아무도 다루지 않았으며 재귀의 특정 지점으로 돌아 오는 것을 처리하지 않습니다 (즉, 원시 재귀가 아님). 모든 재귀를 반복으로 바꿀 수 있다고 말하면 이것이 가능해야합니다.
방금 C # 예제를 생각해 냈습니다. postorder traversal처럼 작동하는 다음과 같은 재귀 함수가 있고 AbcTreeNode가 포인터 a, b, c가있는 3 진 트리라고 가정하십시오.
public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) {
if (x != null) {
AbcRecursiveTraversal(x.a, list);
AbcRecursiveTraversal(x.b, list);
AbcRecursiveTraversal(x.c, list);
list.Add(x.key);//finally visit root
}
}
반복 솔루션 :
int? address = null;
AbcTreeNode x = null;
x = root;
address = A;
stack.Push(x);
stack.Push(null)
while (stack.Count > 0) {
bool @return = x == null;
if (@return == false) {
switch (address) {
case A://
stack.Push(x);
stack.Push(B);
x = x.a;
address = A;
break;
case B:
stack.Push(x);
stack.Push(C);
x = x.b;
address = A;
break;
case C:
stack.Push(x);
stack.Push(null);
x = x.c;
address = A;
break;
case null:
list_iterative.Add(x.key);
@return = true;
break;
}
}
if (@return == true) {
address = (int?)stack.Pop();
x = (AbcTreeNode)stack.Pop();
}
}
답변
재귀 호출을 꼬리 재귀 (마지막 문이 재귀 호출 인 재귀) 로 만들기 위해 노력하십시오 . 일단 당신이 그것을 반복으로 변환하는 것은 일반적으로 매우 쉽습니다.
답변
일반적으로 단순히 스토리지 변수를 사용하여 반복으로 재귀를 모방 할 수 있습니다. 재귀와 반복은 일반적으로 동일합니다. 하나는 거의 항상 다른 것으로 변환 될 수 있습니다. 꼬리 재귀 함수는 반복적 인 함수로 매우 쉽게 변환됩니다. 어큐뮬레이터 변수를 로컬 변수로 만들고 재귀 대신 반복하십시오. 다음은 C ++의 예입니다 (C는 기본 인수를 사용하지 않았습니다).
// tail-recursive
int factorial (int n, int acc = 1)
{
if (n == 1)
return acc;
else
return factorial(n - 1, acc * n);
}
// iterative
int factorial (int n)
{
int acc = 1;
for (; n > 1; --n)
acc *= n;
return acc;
}
나를 알면 코드에서 실수를했을 수도 있지만 아이디어가 있습니다.
답변
스택을 사용해도 재귀 알고리즘을 반복적으로 변환하지는 않습니다. 일반 재귀는 함수 기반 재귀이며 스택을 사용하면 스택 기반 재귀가됩니다. 그러나 여전히 재귀입니다.
재귀 알고리즘의 경우 공간 복잡도는 O (N)이고 시간 복잡도는 O (N)입니다. 반복 알고리즘의 경우 공간 복잡도는 O (1)이고 시간 복잡도는 O (N)입니다.
그러나 복잡성 측면에서 스택을 사용하면 동일하게 유지됩니다. 꼬리 재귀 만 반복으로 변환 할 수 있다고 생각합니다.
답변
스택과 재귀 제거 문서 캡처 힙 스택 프레임을 외부화의 생각은하지만, 제공하지 않습니다 간단하고 반복적 인 변환하는 방법을. 아래는 하나입니다.
반복 코드로 변환하는 동안 재귀 호출은 임의로 깊은 코드 블록에서 발생할 수 있음을 알고 있어야합니다. 그것은 매개 변수뿐만 아니라 실행될 논리와 후속 조건에 참여하는 변수의 상태로 돌아가는 지점이기도합니다. 아래는 최소한의 변경으로 반복 코드로 변환하는 매우 간단한 방법입니다.
이 재귀 코드를 고려하십시오.
struct tnode
{
tnode(int n) : data(n), left(0), right(0) {}
tnode *left, *right;
int data;
};
void insertnode_recur(tnode *node, int num)
{
if(node->data <= num)
{
if(node->right == NULL)
node->right = new tnode(num);
else
insertnode(node->right, num);
}
else
{
if(node->left == NULL)
node->left = new tnode(num);
else
insertnode(node->left, num);
}
}
반복 코드 :
// Identify the stack variables that need to be preserved across stack
// invocations, that is, across iterations and wrap them in an object
struct stackitem
{
stackitem(tnode *t, int n) : node(t), num(n), ra(0) {}
tnode *node; int num;
int ra; //to point of return
};
void insertnode_iter(tnode *node, int num)
{
vector<stackitem> v;
//pushing a stackitem is equivalent to making a recursive call.
v.push_back(stackitem(node, num));
while(v.size())
{
// taking a modifiable reference to the stack item makes prepending
// 'si.' to auto variables in recursive logic suffice
// e.g., instead of num, replace with si.num.
stackitem &si = v.back();
switch(si.ra)
{
// this jump simulates resuming execution after return from recursive
// call
case 1: goto ra1;
case 2: goto ra2;
default: break;
}
if(si.node->data <= si.num)
{
if(si.node->right == NULL)
si.node->right = new tnode(si.num);
else
{
// replace a recursive call with below statements
// (a) save return point,
// (b) push stack item with new stackitem,
// (c) continue statement to make loop pick up and start
// processing new stack item,
// (d) a return point label
// (e) optional semi-colon, if resume point is an end
// of a block.
si.ra=1;
v.push_back(stackitem(si.node->right, si.num));
continue;
ra1: ;
}
}
else
{
if(si.node->left == NULL)
si.node->left = new tnode(si.num);
else
{
si.ra=2;
v.push_back(stackitem(si.node->left, si.num));
continue;
ra2: ;
}
}
v.pop_back();
}
}
코드의 구조가 어떻게 재귀 논리에 여전히 충실하고 수정이 최소화되어 버그 수가 줄어드는 지 살펴보십시오. 비교를 위해 변경 사항을 ++ 및-로 표시했습니다. v.push_back을 제외한 대부분의 새로 삽입 된 블록은 변환 된 반복 논리에 공통입니다.
void insertnode_iter(tnode *node, int num)
{
+++++++++++++++++++++++++
vector<stackitem> v;
v.push_back(stackitem(node, num));
while(v.size())
{
stackitem &si = v.back();
switch(si.ra)
{
case 1: goto ra1;
case 2: goto ra2;
default: break;
}
------------------------
if(si.node->data <= si.num)
{
if(si.node->right == NULL)
si.node->right = new tnode(si.num);
else
{
+++++++++++++++++++++++++
si.ra=1;
v.push_back(stackitem(si.node->right, si.num));
continue;
ra1: ;
-------------------------
}
}
else
{
if(si.node->left == NULL)
si.node->left = new tnode(si.num);
else
{
+++++++++++++++++++++++++
si.ra=2;
v.push_back(stackitem(si.node->left, si.num));
continue;
ra2: ;
-------------------------
}
}
+++++++++++++++++++++++++
v.pop_back();
}
-------------------------
}
