一 递归
递归是用栈来实现的，不用我讲了吧。
不过，递归恐怕不象你想象的这么简单。
首先，它体现了一个数学思想：化归，即把一个问题转化成另一个的方法。
递归比较特殊，它是转化成性质相似，但规模更小的问题。下面请看它的几点
用处：

1.经典递归
例如HANOI塔问题：经典的递归，原问题包含子问题。有些问题或者数据结构本来就是递归描述的，
用递归做很自然。

2.递归与递推
利用递归的思想建立递推关系，如由兔子生崽而来的FIBONACCI数列

3.分治
不少分治方法是源于递归思想，或是递归分解+合并处理。

4.回溯
规模叫小的问题用回溯解决比较自然。注意递归前后要保证现场的保存
和恢复，即正确的转化问题。

5.动态规划
递归+动态修改查表是一种不错的建立动态规划模型的方法。

很多题目，在头绪很多时不妨试试递归！把问题转换成规模更小的问题。

这里举一个例子。
[题目]表达式求值
[分析]
因为是讲递归，不是用栈，当然下面的程序就是用递归实现的了。简单起见，只允许+,-,*,不能有'/',
运算数都是整数且没有一元运算符。

程序思想是把一个字符串分成两个，分别求值，再合并。例如：

3*5-4+2*7

先求2*7=14
再求3*5-4=11
最后11+14=25

如果在括号外有+,-号，找到最右边的(如果是左边的，如上面的例子，分成3*5 和 4+2*7就不对了!)
作为分界，否则只有*就随便找一个括号外的了。注意去掉多余的括号。递归边界是仅含单个数的算式，
用val函数就可以了。

程序清单

program expr;
{
example:
input: 3+4*5-(6-7)
output: 24
}
var
s:string;

{check if an expression is valid}
function ok(s:string):boolean;
var
i,pa:integer;
begin
ok:=false;
pa:=0; {统计左括号的个数}
for i:=1 to length(s) do
begin
if s[i]='(' then inc(pa);
if s[i]=')' then dec(pa);
if pa<0 then exit; {没有左括号与之匹配}
end;
ok:=true;
end;

function exp(s:string):integer;
var
i,k,pa,code:integer;
b,l,r:string;
begin
{去掉多余的括号}
b:=s;
if (b[1]='(')and(b[length(b)]=')')then
begin
delete(b,1,1);
delete(b,length(b),1);
if ok(b) then s:=b; {如果去掉后合法，说明括号真的多余！}
end;

{递归边界}
val(s,k,code);
if code=0 then
begin
exp:=k;
exit;
end;

{2.find P}
i:=length(s); {从最右边开始找}
pa:=0;
while i>0 do
begin
case s[i] of
')':inc(pa);
'(':dec(pa);
'+','-':
if pa=0 then {括号外才行！}
begin
l:=copy(s,1,i-1); {左边}
r:=copy(s,i+1,length(s)-i); {右边}
if s[i]='+' then
begin
exp:=exp(l)+exp(r);
exit;
end;
if s[i]='-' then
begin
exp:=exp(l)-exp(r);
exit;
end;
end;
end;
dec(i);
end;

{only '*'}
for i:=length(s) downto 1 do
if s[i]='*' then {随便找一个}
begin
l:=copy(s,1,i-1);
r:=copy(s,i+1,length(s)-i);
exp:=exp(l)*exp(r);
exit;
end;
end;

begin
readln(s);
writeln(exp(s));
end.

二 分治
分治就是“分而治之”。怎么样，好理解吧？
好是好理解，可是怎么用呢？用递归来实现。这里，“分”是指的分数据，不是分情况。

举一个简单例子。
归并排序：
把a[1],a[2]..a[n]排序，则：
分解：分成a[1]..a[k]和a[k+1],a[k+2]..a[n]两个子序列。
解决：用归并排序（递归了吧！）把两个子序列排序。
合并：把两个已排序的子序列合并

是不是很没有意思？觉得分治很无聊？！非也，非也！看看下面的例题，也许你对分治思想就会有些新的认识。

很多计算几何题目都可以用分治解决，而IOI95的《导线和开关》也是一个不错的例子。
IOI2000的《中等硬度》就是著名的Tom Verhoeff出的一道不错的题目。在这里例子中，分治法就是比较理想
的方法。