基于广义表是递归定义的结构，因此实现广义表操作的算法均为递归函数。 　　何谓"递归函数"？ 　　一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：1) 在每一次调用自己时，必须是(在某种意义上)更接近于解；2) 函数中必须有一个终止处理或计算的准则。例如，在右侧的梵塔函数中，每一次的递归调用，问题规模减少1，在 n=1 时达到"终结状态"，即可直接求解，不再需要继续递归。 　　又如，二叉树的遍历，每一次的递归调用，问题规模缩小为二叉树的左子树或右子树，在子树为空时达到"终结状态"。 　　这两个递归算法都有一个共同特点，即问题求解的方法都是将一个复杂问题分割成若干子问题求解，反之，求得子问题的解之后，原问题也就迎刃而解了。 　　"分割求解(又称分治法)"是进行算法设计的一种方法，其严格定义为： 　　对于一个输入规模为 n 的函数或问题，用某种方法把输入分割成 k(1<k≤n) 个子集，从而产生 个子问题，分别求解这 个问题，得出 个问题的子解，再用某种方法把它们组合成原来问题的解。若子问题还相当大，则可以反复使用分治法，直至最后所分得的子问题足够小，以至可以直接求解为止。 　　在利用分治法求解时，若所得子问题的性质和原问题相同，则可递归求解。 例如：求解焚塔问题 Hanoi(n,x,y,z) 时可将 n 个圆盘分成两组：自上而下的 n-1 个盘和最底下的 n 号盘，从而产生三个子问题： 　　　1) 将上面的 n-1 个盘从 x 轴移到 y 轴； 　　　2) 将下面的 n 号盘从 x 轴移到 z 轴； 　　　3) 将上面的 n-1 个盘从y轴移到 z 轴； 　　依此顺序求解这三个子问题即得到原问题的解。 　　显然，第1和第3个子问题和原问题的性质相同，只是问题规模比原问题小，则可用和求解原问题相同的方法求解，而第2个问题可以直接求解。对应于原问题求解的函数 Hanoi(n,x,y,z)，第1和第3个子问题求解的函数分别为 　　　　Hanoi(n-1,x,z,y)　和　Hanoi(n-1,y,x,z) 　　显然，n=1 时可以直接求解，由此得到右侧的递归函数。 又如，在对二叉树进行遍历时，可将二叉树中结点分成根结点、左子树和右子树三部分，从而引出三个子问题： 　　　1) 访问根结点； 　　　2) 先序遍历左子树； 　　　3) 先序遍历右子树。 　　按任意次序完成这三个子问题，即求得原问题的解。 　　显然，第1个问题是简单问题，可以直接求解，而第2和第3个问题的性质和原问题相同，则可递归求解，且递归的终结状态是二叉树为空树。

void hanoi(int n,char x,char y,char z) { 　// 将 x 轴上自上而下编号依次为1至 n 的 　// n 个盘移到 z 轴上，y 轴为中间过渡用轴 　if (n==1) move(x, 1, z); 　else { 　　hanoi(n-1,x,z,y); 　// 将 x 轴上自上而下编号依次为1至 n-1的 n-1个 　// 盘移到 y 轴上，z 轴为中间过渡用轴 　　move(x,n,z); 　// 将编号为 n 的盘从 x 轴直接移到 z 轴上 　　hanoi(n-1,y,x,z); 　// 将 y 轴上自上而下编号依次为1至n-1的n-1个 　// 盘移到 z 轴上，x 轴为中间过渡用轴 　} } // hanoi void PreOrderTraverse( BiTree T, 　　　　　　　　　　void (*visit)(BiTree)) { 　// 先序遍历T为指向根结点的指针的二叉树， 　// visit 为结点的访问函数 　if (T) 　{ visit(T); 　　PreOrderTraverse( T->lchild,visit); 　// 先序遍历 T->lchild 所指二叉树 　　PreOrderTraverse( T->rchild,visit); 　// 先序遍历 T->rchild 所指二叉树 　} } // PreOrderTraverse