# 从recursion到迭代的方法

• 有一般规定吗？
• 有没有“模式”？

### 18 Solutions collect form web for “从recursion到迭代的方法”

``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);` `

` `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; } }` `

` `public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) { if (x != null) { AbcRecursiveTraversal(xa, list); AbcRecursiveTraversal(xb, list); AbcRecursiveTraversal(xc, 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 = xa; address = A; break; case B: stack.Push(x); stack.Push(C); x = xb; address = A; break; case C: stack.Push(x); stack.Push(null); x = xc; address = A; break; case null: list_iterative.Add(x.key); @return = true; break; } } if (@return == true) { address = (int?)stack.Pop(); x = (AbcTreeNode)stack.Pop(); } }` `

` `// 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; }` `

` `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 // eg, 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(); } }` `

` `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(); }` `

`-------------------------`

` `}` `

search谷歌的“继续传递风格”。 有一个转换为尾recursion风格的一般程序; 还有一个把尾recursion函数转换成循环的一般过程。

` `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); }` `

` `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); } }` `

` `void foo(Node* node) { if(node == NULL) return; // Do something with node... foo(node->left); foo(node->right); }` `

` `void foo(Node* node) { while(node != NULL) { // Do something with node... foo(node->left); node = node->right; } }` `

recursion不过是从另一个函数调用另一个函数的过程，只有通过调用函数本身才能完成。 正如我们所知，当一个函数调用另一个函数时，第一个函数会保存其状态（variables），然后将控制权交给被调用的函数。 被调用函数可以通过使用相同名称的variables来调用，例如fun1（a）可以调用fun2（a）。 当我们做recursion调用时，没有新的事情发生。 一个函数通过在名称variables中传递相同的types和类似的名称（但显然存储在variables中的值不同，只有名称保持不变）。 但在每次调用之前，函数都会保存其状态，并继续保存这个过程。 节省是在一个堆栈上完成的。

certificate是简单和分析的。

` `typedef struct { int32_t type; int32_t valueint; double valuedouble; struct cNODE *next; struct cNODE *prev; struct cNODE *child; } cNODE;` `

recursion删除function如下所示：

` `void cNODE_Delete(cNODE *c) { cNODE*next; while (c) { next=c->next; if (c->child) { cNODE_Delete(c->child) } free(c); c=next; } }` `

` `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; } }` `

` `function show(node) 0. if isleaf(node): 1. print node.name 2. else: 3. show(node.left) 4. show(node) 5. show(node.right)` `

` `function rec(...) { for/while loop { var x = rec(...) // make a side effect involving return value x } }` `

` `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())); } }` `

• 我如何摆脱斯卡拉循环？
• 序言累加器。 他们真的是一个“不同”的概念吗？
• 为什么Ocaml / F＃中的函数默认不recursion？
• 在嵌套的python字典和列表中查找所有出现的键
• 一步定义和调用function
• recursion函数从数据库结果生成multidimensional array
• 用列表返回Pythonrecursion无
• 在Java中使用recursion的因子
• recursion或迭代？
• recursion层次 - 使用Linq的recursion查询
• 如何在JavaScript中了解蹦床？