# recursion - 递归算法 - 递归迭代回溯

## 从递归到迭代的方法 (12)

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

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

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

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

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

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

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

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

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

``````stack.push(new Task(size, from, to, spare));
while(! stack.isEmpty()) {