怎样才能深刻理解递归和回溯？

递归的精华就在于大问题的分解，要学会宏观的去看问题，如果这个大问题可以分解为若干个性质相同的规模更小的问题，那么我们只要不断地去做分解，当这些小问题分解到我们能够轻易解决的时候，大问题也就能迎刃而解了。如果你能独立写完递归创建二叉树，前序、中序、后序递归遍历以及递归计算二叉树的最大深度，递归就基本能掌握了。

回溯本人用得很少，仅限于八皇后问题，所以帮不上啥了。

递归是一种算法结构，回溯是一种算法思想，一个递归就是在函数中调用函数本身来解决问题，回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”，意思就是对已经知道错误的结果没必要再枚举接下来的答案了，比如一个有序数列1,2,3,4,5，要找和为5的所有集合，从前往后搜索我选了1，然后2，然后选3 的时候发现和已经大于预期，那么4,5肯定也不行，这就是一种对搜索过程的优化。
回溯分析是追踪决策的特性之一。 是指对原始决策的产生机制、决策内容、主客观环境等进行分析．从起点开始，按顺序考察导致决策失误的原因、问题的性质、失误的程度等。
[算法分析]
为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自已来定义自己的方法，称为递归定义。例如：定义函数f(n)为：
f(n)=n*f(n－1) (n>0)
f(n)=1 (n=0)
则当0时，须用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)……当n=0时，f(n)=1。
由上例我们可看出，递归定义有两个要素：
（1）递归边界条件。也就是所描述问题的最简单情况，它本身不再使用递归的定义。
如上例，当n=0时，f(n)=1，不使用f(n-1)来定义。
（2）递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。
如上例：f(n)由f(n-1)定义，越来越靠近f(0),也即边界条件。最简单的情况是f(0)=1。
递归算法的效率往往很低, 费时和费内存空间. 但是递归也有其长处, 它能使一个蕴含递归关系且结构复杂的程序简介精炼, 增加可读性. 特别是在难于找到从边界到解的全过程的情况下, 如果把问题推进一步,其结果仍维持原问题的关系, 则采用递归算法编程比较合适.
递归按其调用方式分为: 1. 直接递归, 递归过程P直接自己调用自己; 2. 间接递归, 即P包含另一过程D, 而D又调用P.
递归算法适用的一般场合为:
1. 数据的定义形式按递归定义.
如裴波那契数列的定义: f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2.
对应的递归程序为:
Function fib(n : integer) : integer;
Begin
if n = 0 then fib := 1 { 递归边界 }
else if n = 1 then fib := 2
else fib := fib(n-2) + fib(n-1) { 递归 }
End;
这类递归问题可转化为递推算法, 递归边界作为递推的边界条件.
2. 数据之间的关系(即数据结构)按递归定义. 如树的遍历, 图的搜索等.
3. 问题解法按递归算法实现. 例如回溯法等.
从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到" 尽头 "
的时候, 再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断" 回溯 "寻找解的方法, 称作
" 回溯法 ".

[参考程序]
下面给出用回溯法求所有路径的算法框架. 注释已经写得非常清楚, 请读者仔细理解.
Const maxdepth = ????;
Type statetype = ??????; { 状态类型定义 }
operatertype = ??????; { 算符类型定义 }
node = Record { 结点类型 }
state : statetype; { 状态域 }
operater :operatertype { 算符域 }
End;
{ 注: 结点的数据类型可以根据试题需要简化 }
Var
stack : Array [1..maxdepth] of node; { 存当前路径 }
total : integer; { 路径数 }
Procedure make(l : integer);
Var i : integer;
Begin
if stack[L-1]是目标结点 then
Begin
total := total+1; { 路径数+1 }
打印当前路径[1..L-1];
Exit
End;
for i := 1 to 解答树次数 do
Begin
生成 stack[l].operater;
stack[l].operater 作用于 stack[l-1].state, 产生新状态 stack[l].state;
if stack[l].state 满足约束条件 then make(k+1);
{ 若不满足约束条件, 则通过for循环换一个算符扩展 }
{ 递归返回该处时, 系统自动恢复调用前的栈指针和算符, 再通过for循环换一个算符扩展 }
{ 注: 若在扩展stack[l].state时曾使用过全局变量, 则应插入若干语句, 恢复全局变量在
stack[l-1].state时的值. }
End;
{ 再无算符可用, 回溯 }
End;
Begin
total := 0; { 路径数初始化为0 }
初始化处理;
make(l);
打印路径数total
End.