数组递归

一句话理解

数组递归：把“处理整个数组”变成“处理一个元素 + 处理剩下的”。

为什么要学

为后面的分治、线段树建立感觉。

讲解

例如求和：sum(l,r)=a[l]+sum(l+1,r)，l>r 时为 0。也可以对半切。

能循环就循环。这里的重点是思考方式，不是为了把求和写得更慢。

例子

int sum(int a[], int l, int r) {
    if (l > r) return 0;
    return a[l] + sum(a, l + 1, r);
}

每次拿走最左元素，直到区间空。

常见错误

• 出口写成 l==r 却忘了空区间。
• 每次复制整个数组当参数，又慢又占内存。