今日新知（关于递归中变量的声明）

在递归函数中用到的变量，要将它声明为局部变量，切记不能声明为全局变量。

如下面归并排序中的变量k。

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 const int N = 100010;
 6 
 7 int a[N],b[N];
 8 
 9 int n ;
10 long long res = 0 ; 
11 
12 void merge_sort(int a[],int l,int r){
13     
14     if(l >= r) return ;
15     
16     int mid = l + r >> 1;
17     
18     int k = 0;
19     
20     int i = l , j = mid + 1;
21     merge_sort(a,l,mid);
22     merge_sort(a,mid+1,r);
23     while(i <= mid && j <= r){
24         if(a[i] <= a[j]) b[k ++] = a[i ++];
25         else {
26             b[k ++] = a[j ++];
27             res += mid - i + 1;
28         }
29     }
30     while(i <= mid) b[k ++] = a[i ++];
31     while(j <= r) b[k ++] = a[j ++];
32     
33     for(int i = l , j  = 0 ;  i <= r ; i ++ , j ++) a[i] = b[j];
34 }
35 
36 int main(){
37     cin >> n;
38     for(int i = 0 ; i < n ; i ++) scanf("%d",&a[i]);
39     
40     merge_sort(a,0,n - 1);
41     
42     cout << res;
43     
44     return 0;
45 
46 }

View Code

如果声明成局部变量，那每次调用merge_sort()时，都会创建一个 k，第一层中的 k 和第二层中的没关系
如果声明成全局的，每一层中的 k 都是同一个，这一层中k变了，下一层也会变化，所以下层中的循环会“提前”结束.

如果把 k 声明为全局变量，显然是不行的，你每次调用merge_sort()都会改变 k 的值，那么回溯后，其作为索引的意义就已经被破坏了。

局部变量每次调用函数都不是同一个，全局变量则是同一个。因为函数有递归调用，如果是局部变量，每次调用的 k 都是相互独立的，
而如果是全局变量，则是同样的 k。