一个递归函数的运行过程类似于多个函数的嵌套调用，差别仅在于"调用函数和被调用函数是同一个函数"。为了保证"每一层的递归调用"都是对"本层"的数据进行操作，在执行递归函数的过程中需要一个"递归工作栈"。它的作用是:一、将递归调用时的实在参数和函数返回地址传递给下一层执行的递归函数；二、保存本层的参数和局部变量，以便从下一层返回时重新使用它们。
递归过程执行过程中所占用的数据区，称之为递归工作栈。
每一层的递归参数等数据合成一个记录，称之为递归工作记录。
栈顶记录指示当前层的执行情况，称之为当前活动记录。
递归工作栈的栈顶指针，称之为当前环境指针。
递归函数执行过程中递归工作栈的工作情况可用大家熟悉的"梵塔函数"为例，请看动画演示。
算法3.3void hanoi (int n, char x, char y, char z, int &i )
// 将塔座 x 上按直径由小到大且至上而下编号为1至 n
// 的 n 个圆盘按规则搬到塔座 z 上，y 可用作辅助塔座。
1 {
2 if (n==1)
3 {
4 move(x, 1, z); // 将编号为1的圆盘从 x 移到 z
5 i++;
6 }
7 else {
8 hanoi(n-1, x, z, y); // 将 x 上编号为1至 n-1 的圆盘移到 y,z 作辅助塔
9 move(x, n, z); // 将编号为 n 的圆盘从 x 移到 z
10 i++;
11 hanoi(n-1, y, x, z); // 将 y 上编号为1至 n-1 的圆盘移到 z,x 作辅助塔
12 }
13}
在此，称调用递归函数的主函数为"第0层"，则从主函数调用递归函数被称为进入递归函数的 "第1层" ，从递归函数的"第i层"递归调用本函数被称为进入递归函数的"第 i+1 层"。显然，当递归函数执行到第 i 层时，从第1层到第 i-1 层的数据都必须被保存下来，以便一层一层退回时继续使用。递归函数执行过程中每一层所占用的内存数据区合起来就是一个 "递归工作栈"。