迭代乃人工，递归方神勇。

To iterate is human, to recurse, divine.

（神通的原因在于编译器在背后利用函数栈帧的数据结构。）

凡治众如治寡，分数是也。

The control of a large force is the same principle as the control of a few men: it is merely a question of dividing up their numbers.

分数，可以减而治之（Decrease and conquer），也可以分而治之（Divide and conquer）。

1 减而治之

demo:

#include int Sum(int arr[],int size){    if(size<1)        return 0;    return arr[size-1]+Sum(arr,size-1);          // 单递归，线性递归}int main(){    int arr[] = {1,2,3,4,5};    int n = sizeof arr / sizeof *arr;    printf("%d\n",Sum(arr,n-1));    getchar();}

线性递归：

2 分而治之

demo:

#include int Sum(int arr[],int lo,int hi){    if(lo==hi)        return arr[lo];    int mid = (lo+hi)>>1;    return Sum(arr,lo,mid)+Sum(arr,mid+1,hi); // 双递归，二叉树形式递归}int main(){    int arr[] = {1,2,3,4,5};    int n = sizeof arr / sizeof *arr;    printf("%d\n",Sum(arr,0,n-1));    getchar();}

二叉树形式递归：

－End－