若一个对象部分地包含自己，或用自己给自己定义，则这个对象是递归的；若一个过程调用自己，则这个过程也是递归的。
概念
以下3种情况，常常会用到递归。
定义是递归的
如阶乘、幂函数、裴波那契等。
long Factorial(long n) {
if (n == 0) {
return 1;
} else {
return n * Factorial(n - 1);
}
}数据结构是递归的
链表就是一种递归的数据结构。而树是用多重链表实现的，所以也是递归的结构。所以链表和树的一些算法，可以用递归过程来实现。
例如，搜索单链表最后一个节点的递归解法：
LinkNode *FindRear(LinkNode *f) {
if (f == NULL) {
return NULL
} else if (f->link == NULL) {
return f;
} else {
return FindRear(f->link);
}
};单链表搜索给定值的节点：
void Search(LinkNode *f, T& x) {
if (f == NULL) {
return NULL;
} else if (f->data == x) {
return f;
} else {
Search(f->link, x)
}
};问题的解法是递归的
典型的就是汉诺塔。
#include <iostream.h>
#include <string.h>
void Hanoi(int n, String A, String B, String C) {
if (n == 1) {
cout << "Move top disk from peg " << A << " to peg " << C << endl;
} else {
Hanoi(n - 1, A, C, B);
cout << "Move top disk from peg " << A << " to peg " << C << endl;
Hanoi(n - 1, B, A, C);
}
};递归过程与递归工作栈
递归工作栈
每一层递归调用所需保存的信息构成一个工作记录。通常包括： 1.返回地址 2.在本次过程调用时，为与形参结合的实参创建副本 3.本层的局部变量值
每进入一层递归，系统就要建立一个新的工作记录，把上述项目登入，加到递归工作栈的栈顶。每退出一层递归，就从递归工作栈退出一个工作记录。
用栈实现递归过程的非递归算法
对于递归过程，可以利用栈将它改为非递归过程。以求裴波那契数列为例：
struct Node {
long n;
int tag;
};
long Fibnacci(long n) {
Stack<Node> S;
Node *w;
long sum = 0;
do {
while (n > 1) {
w->n = n;
w->tag = 1;
S.Push(w);
n--;
}
sum = sum + n;
while (S.IsEmpty() == false) {
S.Pop(w);
if (w->tag == 1) {
w->tag = 2;
S.Push(w);
n = w->n - 2;
break;
}
}
} while (S.IsEmpty() == false);
return sum;
};用迭代法实现递归过程
一般对尾递归或单向递归的情形，都可以利用迭代的方法，将递归过程改为非递归过程。
如计算斐波那契数列的非递归算法：
long FibIter(long n) {
if (n <= 1) {
return n;
}
long twoback = 0, oneback = 1, Current;
for (int i = 2; i <= n; i ++) {
Current = twoback + oneback;
twoback = oneback;
oneback = Current;
}
return Current;
}回溯法
用回溯法求解问题时常常使用递归方法进行试探，或使用栈帮助向前试探和回溯。以迷宫问题为例。
前进方向表的定义。
struct offsets {
int a, b;
char *dir;
};
offsets move[8];递归解法。
int SeekPath(int x, int y) {
int i, g, h;
char *d;
if (x == m && y == p) {
return 1;
}
for (i = 0; i < 8; i ++) {
g = x + move[i].a;
h = y + move[i].b;
d = move[i].dir;
if (Maze[g][h] == 0 &R& mark[g][h] == 0) {
mark[g][h] = 1;
if (SeekPath(g, h)) {
cout << "(" << g << "," << h << "),"
<< "Direction" << dir << ",";
return 1;
}
}
}
if (x == 1 && y == 1) {
cout << "no path in Maze" << endl;
}
return 0;
};为了将递归算法改为非递归算法，需要使用一个栈来存储在试探的过程中所走过的路径。一旦需要回退，可以从栈中取得刚才走过位置的座标和前进方向。栈中需要保存一系列三元组以记录这些信息。
struct items {
int x, y, dir;
};迷宫问题的非递归算法如下。
void path(int m, int p) {
int i, j, d, g, h;
mark[1][0] = 1;
Stack<items> st(m * p);
items tmp;
st.Push(tmp);
while (st.IsEmpty() == false) {
st.Pop(tmp);
i = tmp.x;
j = tmp.y;
d = tmp.dir;
while (d < 8) {
g = i + move[d].a;
h = i + move[d].b;
if (g == m && h == p) {
cout << st;
cout << m << " " << p << endl;
return;
}
if (Maze[g][h] == 0 && mark[g][h] == 0) {
mark[g][h] = 1;
tmp.x = i;
tmp.y = j;
tmp.dir = d;
st.Push(tmp);
i = g;
j = h;
d = 0;
} else {
d ++;
}
}
}
cout << "no path" << endl;
};
ostream& operator << (ostream& os, items& item) {
return os << item.x << "," << item.y << "," << item.dir;
};