재귀에서 반복으로 가는 방법
https://stackoverflow.com/questions/159590
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 간단한 문제를 해결하기 위해 수년간의 프로그래밍에서 재귀를 많이 사용해왔지만 때로는 메모리/속도 문제로 인해 반복이 필요하다는 것을 잘 알고 있습니다.
그래서 아주 먼 옛날에 나는 일반적인 재귀 접근 방식을 반복으로 변환하는 "패턴"이나 교과서 방법이 있는지 찾으려고 노력했지만 아무것도 찾지 못했습니다.아니면 적어도 내가 기억하는 어떤 것도 도움이 되지 않을 것입니다.
- 일반적인 규칙이 있나요?
- "패턴"이 있습니까?
해결책
일반적으로 반복 알고리즘으로 재귀 알고리즘을 반복적 인 알고리즘으로 대체하여 일반적으로 재귀 함수로 전달되는 매개 변수를 스택으로 전달합니다. 실제로, 당신은 프로그램 스택을 자신의 것 중 하나로 교체하고 있습니다.
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# 예를 생각해 냈습니다. 다음과 같은 재귀 함수를 가지고 있는데,이 기능은 우편 주문형 트래버스처럼 작용하고 Abctreenode가 Pointers 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)입니다.
그러나 스택을 사용하면 복잡성 측면에서 동일하게 유지됩니다.tail recursion만이 iteration으로 변환될 수 있다고 생각합니다.
그만큼 스택 및 재귀 제거 기사는 힙의 스택 프레임을 외부화한다는 아이디어를 캡처하지만 간단하고 반복 가능합니다 변환하는 방법. 아래는 하나입니다.
반복 코드로 변환하는 동안 재귀 호출은 임의로 깊은 코드 블록에서 발생할 수 있음을 알고 있어야합니다. 그것은 매개 변수뿐만 아니라 실행중인 논리로 돌아가는 지점과 후속 조건부에 참여하는 변수의 상태에도 중요합니다. 아래는 최소한 변경으로 반복 코드로 변환하는 매우 간단한 방법입니다.
이 재귀 코드를 고려하십시오.
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();
}
-------------------------
}
"계속 통과 스타일"을 검색하십시오. 꼬리 재귀 스타일로 변환하는 일반적인 절차가 있습니다. 꼬리 재귀 함수를 루프로 돌리는 일반적인 절차도 있습니다.
그냥 죽이는 시간 ... 재귀 기능
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
변환 할 수 있습니다
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
stack.push(node->right);
stack.push(node->left);
while(!stack.empty()) {
node1 = stack.pop();
if(node1 == NULL)
continue;
// Do something with node1...
stack.push(node1->right);
stack.push(node1->left);
}
}
일반적으로 스택 오버 플로우를 피하는 기술은 재귀 함수를위한 기술을 Java Devs에 의해 널리 채택하는 트램폴린 기술이라고합니다.
그러나 C#의 경우 약간의 도우미 방법이 있습니다. 여기 이는 논리를 변경하거나 코드를 이해할 수 없게 만들 필요없이 재귀 기능을 반복적으로 바꿉니다. C#은 놀라운 언어로 놀라운 것들이 가능합니다.
도우미 방법으로 방법의 일부를 감싸서 작동합니다. 예를 들어 다음과 같은 재귀 기능 :
int Sum(int index, int[] array)
{
//This is the termination condition
if (int >= array.Length)
//This is the returning value when termination condition is true
return 0;
//This is the recursive call
var sumofrest = Sum(index+1, array);
//This is the work to do with the current item and the
//result of recursive call
return array[index]+sumofrest;
}
로 바뀝니다 :
int Sum(int[] ar)
{
return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
.RecursiveCall((i, rv) => i + 1)
.Do((i, rv) => ar[i] + rv)
.Execute(0);
}
실제로 스택이 필요한 것들에 대한 생각 :
재귀 패턴을 다음과 같이 고려한다면
if(task can be done directly) {
return result of doing task directly
} else {
split task into two or more parts
solve for each part (possibly by recursing)
return result constructed by combining these solutions
}
예를 들어, 하노이의 고전적인 타워
if(the number of discs to move is 1) {
just move it
} else {
move n-1 discs to the spare peg
move the remaining disc to the target peg
move n-1 discs from the spare peg to the target peg, using the current peg as a spare
}
이것은 명시 적 스택에서 작업하는 루프로 변환 될 수 있습니다.
place seed task on stack
while stack is not empty
take a task off the stack
if(task can be done directly) {
Do it
} else {
Split task into two or more parts
Place task to consolidate results on stack
Place each task on stack
}
}
하노이 타워의 경우 : 이것은 다음과 같습니다.
stack.push(new Task(size, from, to, spare));
while(! stack.isEmpty()) {
task = stack.pop();
if(task.size() = 1) {
just move it
} else {
stack.push(new Task(task.size() -1, task.spare(), task,to(), task,from()));
stack.push(new Task(1, task.from(), task.to(), task.spare()));
stack.push(new Task(task.size() -1, task.from(), task.spare(), task.to()));
}
}
스택을 어떻게 정의하는지에 대한 상당한 유연성이 있습니다. 스택을 목록으로 만들 수 있습니다 Command 정교한 일을하는 대상. 또는 반대 방향으로 가서 더 간단한 유형의 목록으로 만들 수 있습니다 (예 : "작업"은 스택에 4 가지 요소 일 수 있습니다. int, 스택에 하나의 요소보다는 Task).
이 모든 것은 스택의 메모리가 Java 실행 스택이 아닌 힙에 있다는 것을 의미하지만,이를 더 많이 제어 할 수 있다는 것이 유용 할 수 있습니다.
찾아야 할 패턴 중 하나는 함수 끝에서 재귀 호출 (소위 테일 리퍼션)입니다. 이것은 쉽게 한동안 대체 될 수 있습니다. 예를 들어, 함수 foo :
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
Foo에게 전화를 걸어 끝납니다. 이것은 다음과 같이 대체 할 수 있습니다.
void foo(Node* node)
{
while(node != NULL)
{
// Do something with node...
foo(node->left);
node = node->right;
}
}
두 번째 재귀 호출을 제거합니다.
방금 올바른 솔루션이라고 생각하는 명백한 스택을 사용하는 것이 좋습니다.
반복적 인 기능으로 재귀 함수를 변환하는 데 사용할 수 있습니다. 재귀적인 호출에 걸쳐 저장되는 값을 확인하십시오. 가지다 재귀 함수에 로컬에 있으려면 통화를 스택에 밀어 넣을 주기로 교체하십시오. 스택이 비어 있으면 재귀 함수가 종료되었을 것입니다.
나는 모든 재귀 함수가 다른 데이터 유형의 반복적 인 함수와 동일하다는 증거가 내 대학 시대에 대한 나의 가장 소중한 기억 중 하나라고 말할 수는 없습니다. 그것은 컴퓨터 프로그래밍이 무엇인지 실제로 이해하게 한 과정 (및 교수)이었습니다.
ㅏ 의문 이 하나의 복제물로 닫혔습니다. 매우 구체적인 데이터 구조가 있습니다.
노드에는 다음과 같은 구조가있었습니다.
typedef struct {
int32_t type;
int32_t valueint;
double valuedouble;
struct cNODE *next;
struct cNODE *prev;
struct cNODE *child;
} cNODE;
재귀 삭제 함수는 다음과 같습니다.
void cNODE_Delete(cNODE *c) {
cNODE*next;
while (c) {
next=c->next;
if (c->child) {
cNODE_Delete(c->child)
}
free(c);
c=next;
}
}
일반적으로, 한 번 이상 (또는 한 번) 자신을 호출하는 재귀 함수에 대한 스택을 피하는 것이 항상 가능하지는 않습니다. 그러나이 특정 구조의 경우 가능합니다. 아이디어는 모든 노드를 단일 목록으로 평평하게하는 것입니다. 이것은 현재 노드를 넣음으로써 달성됩니다 child 상단 행 목록의 끝에.
void cNODE_Delete (cNODE *c) {
cNODE *tmp, *last = c;
while (c) {
while (last->next) {
last = last->next; /* find last */
}
if ((tmp = c->child)) {
c->child = NULL; /* append child to last */
last->next = tmp;
tmp->prev = last;
}
tmp = c->next; /* remove current */
free(c);
c = tmp;
}
}
이 기술은 결정 론적 토폴로지 순서로 DAG로 줄일 수있는 모든 데이터 연결된 구조에 적용될 수 있습니다. 현재 노드 어린이는 재배치되어 마지막 어린이가 다른 모든 어린이를 입양하도록합니다. 그런 다음 현재 노드를 삭제하고 횡단이 나머지 자식으로 반복 할 수 있습니다.
재귀는 한 기능을 다른 기능으로부터 호출하는 과정에 지나지 않습니다.이 프로세스 만 기능 자체를 호출하여 수행됩니다. 한 함수가 다른 함수를 호출 할 때 알다시피 첫 번째 함수는 상태 (변수)를 저장 한 다음 컨트롤을 호출 함수로 전달합니다. 동일한 이름의 변수를 사용하여 호출 함수를 호출 할 수 있습니다. 우리가 재귀 적 전화를 할 때 아무것도 새로운 일이 일어나지 않습니다. 하나의 함수는 동일한 유형을 전달하고 이름 변수가 유사하게 전달되어 자체를 호출합니다 (분명히 변수에 저장된 값은 다르고 이름 만 동일하게 유지됩니다). 그러나 모든 호출 전에 함수는 상태를 저장 하고이 절약 프로세스는 계속됩니다. 저축은 스택에 이루어집니다.
이제 스택이 작용합니다.
따라서 반복 프로그램을 작성하고 매번 스택에 상태를 저장 한 다음 필요할 때 스택에서 값을 팝업하면 재귀 프로그램을 반복적 인 프로그램으로 성공적으로 변환했습니다!
증거는 간단하고 분석적입니다.
재귀에서 컴퓨터는 스택을 유지하고 반복 버전에서는 스택을 수동으로 유지해야합니다.
그것에 대해 생각하고, 깊이 첫 번째 검색 (그래프) 재귀 프로그램을 DFS 반복 프로그램으로 변환하십시오.
모두 제일 좋다!
시스템이 재귀 기능을 취하고 스택을 사용하여 실행하는 방법에 대한 대략적인 설명 :
이것은 세부 사항없이 아이디어를 보여 주려고했습니다. 그래프의 노드를 인쇄하는이 기능을 고려하십시오.
function show(node)
0. if isleaf(node):
1. print node.name
2. else:
3. show(node.left)
4. show(node)
5. show(node.right)
예를 들어 그래프 : A-> B A-> C Show (a)는 B, A, C를 인쇄합니다.
함수 호출은 로컬 상태와 연속 지점을 저장하므로 돌아와서 호출하려는 기능을 뛰어 넘을 수 있습니다.
예를 들어, 쇼 (a)가 실행되기 시작한다고 가정합니다. 3 행에서의 함수 호출은 쇼 (b)를 의미합니다 - 스택에 항목 추가 "로컬 변수 상태 노드 = A와 함께 라인 2에서 계속해야합니다" - 노드 = b를 가진 GOTO 행 0.
코드를 실행하기 위해 시스템은 지침을 통해 실행됩니다. 함수 호출이 발생하면 시스템은 정보 코드로 돌아와서 기능 코드를 실행해야하며 함수가 완료되면 계속 해야하는 위치에 대한 정보를 팝업합니다.
이것 링크 몇 가지 설명을 제공하고 "위치"를 유지하려면 여러 재귀 콜 사이의 정확한 위치에 도달 할 수 있다는 아이디어를 제안합니다.
그러나이 모든 예는 재귀적인 호출이 이루어지는 시나리오를 설명합니다. 결정된 시간의 양. 다음과 같은 것이 있으면 상황이 까다로워집니다.
function rec(...) {
for/while loop {
var x = rec(...)
// make a side effect involving return value x
}
}
여러 반복기 공급 업체 (반복자를 반환하는 Lambda Expression)를 연결하는 게으른 반복기를 사용하여 재귀 트래버스를 반복자로 변환하는 일반적인 방법이 있습니다. 내 참조 재귀 트래버스를 반복자로 변환합니다.
재귀 함수를 스택을 사용하여 반복적 인 기능으로 바꾸는 또 다른 간단하고 완전한 예.
#include <iostream>
#include <stack>
using namespace std;
int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }
struct Par
{
int a, b;
Par() : Par(0, 0) {}
Par(int _a, int _b) : a(_a), b(_b) {}
};
int GCDIter(int a, int b)
{
stack<Par> rcstack;
if (b == 0)
return a;
rcstack.push(Par(b, a % b));
Par p;
while (!rcstack.empty())
{
p = rcstack.top();
rcstack.pop();
if (p.b == 0)
continue;
rcstack.push(Par(p.b, p.a % p.b));
}
return p.a;
}
int main()
{
//cout << GCD(24, 36) << endl;
cout << GCDIter(81, 36) << endl;
cin.get();
return 0;
}
