[C++知识库]C++递归以及内存值的传递

递归

递归其实是函数的自我调用。
如果一个函数可以求A(n)，那么就一定可以求解A(n-1)，就形成了递归调用。

递归求解问题的过程

第一步:找出规律(其实一般来说规律是很容易找出来的，但是很难用代码来实现)
第二步:写函数，此函数的返回值是调用自己本身。
第三步:寻找起始项，使递归停止。这一步很重要！！！不然会使函数称为死循环。

递归的重要思想

既然一个函数func()可以解决一个问题的第n步那么肯定可以解决第n-1步，同理也能解决第n+1步。
既然一个函数func()可以求解第n项，那么肯定可以求n-1项以及n+1项。

值的传递与地址传递

我们先来看一个程序

void func1(int x){
x++;}
void func2(int a[]){
a[0]++;}
int main(){
int x=1;
func1(x);
cout<<x<<endl;//这个x不是func1中的x

int a[3]={0};//初始化全为0
func2[a];
cout<<a[0];}

问题是现在打印出的x以及a[0]的值是多少，我起先认为都是2.这其实是错误的。正确答案是x是1，a[0]是2.
这是为什么呢？

那么我们先引入两个概念。
地址:变量在内存中的编号；比如一维数组的本质是a[0]的地址。
指针:地址在C++中叫做指针。
比如我们不能直接打印a，会得到一个十六进制数。

int main(){
int a[3]={0};
cout<<a<<endl;//会得到一个以0x开头的数，表示16进制
int b=0x1a;
cout<<b<<endl;//26
int c=017;
cout<<c<<endl;//15 0开头表示8进制数
}

这个程序的原理是:
1、每个函数运行时会生成一个独立的内存，来存储函数内部定义的变量，因此函数互相看不到彼此内部定义的变量名，也不会出现变量名冲突的情况；
2、向函数中传递整数本质是将整数的值拷贝给函数；向函数中传递数组，本质是将数组的地址拷贝给函数；(看到这里应该可以明白为什么x是1而a[0]是2了吧！)
整数比较好理解，数组比较抽象：
其实数组名a存储的就是a[0]的地址，如果想访问a[1]就要把a[0]的地址+1。那么把数组传给func2就相当于把a的地址给了func2，再func2内调用a[0]++,就相当于通过地址找到a[0]，再++。而a[0]实际是存储在main函数中(func2中只是a的地址，可以通过打印func2中的a的地址与main中的a的地址来测试是否是同一个地址。其实func2的int a[]可以看作是一个数组指针，指向a)，也就改变了a[0]的值。
意思就是main函数中的x与func1中的x并不是同一个x；而main函数中的数组a与func2中的数组a却是同一个。关键看的是传给函数的是一个整数还是一个数组的地址。