登录以参加训练计划

递归

在学习递归前，我们需要再一次复习下之前函数的相关知识。

一、形参与实参

函数的形参和在函数内部定义的定义的变量都被称为该函数的局部变量。不同的函数的局部变量相互独立。即无法访问其它函数的局部变量。需要注意的是局部变量的存储空间是临时分配的，函数执行完毕时，局部变量的空间将被释放，其中的值无法保留到下次使用。与此对应的是全局变量，它在函数外声明，可以被任何函数使用。

二、调用栈

我们看一下函数的调用过程，函数的调用过程可以简单理解成，计算实参的值，赋值给对应的形参，然后把“当前代码行”转移到函数的首部，那么函数执行完成后，函数又做了些什么呢？有返回值的把返回值返回给调用它的函数，然后再次“修改当前代码行”，恢复到调用它的地方执行向下执行。但是计算机是如何知道该返回到哪一行继续执行呢？为了解这个问题，我们需要知道“调用栈”。

调用栈描述的是函数之间的调用关系。它由多个栈帧（Stack Frame）组成，每个栈帧对应着一个未行完的函数。栈帧中保存了该函数的返回地址和局部变量，因而不仅能在执行完毕后找到正确的返回地址，还很自然地保证了不同函数间的局部变量互不相干--因为不同的函数对应不同的栈帧。 C语言中用调用栈（Call Stack）来描述函数之间的调用关系。调用栈由栈帧（Stack Frame）组成，每个栈帧对应着一个未运行完的函数。在gdb中可以用backtrace(bt)命令打印所有栈帧的信息。若要用p命令打印一个非当前栈帧的局部变量，可以用frame命令选择另一个栈帧。

以下命令可以详细查看函数调用栈帧情况：

C:\Program Files (x86)\Dev-Cpp\MinGW64\bin>g++ a.cpp -g

C:\Program Files (x86)\Dev-Cpp\MinGW64\bin>gdb a.exe

(gdb) l//list 列表显示

(gdb) b 8//break at 8 设置断点

(gdb) r//run 运行程序

(gdb) bt//backtrack 打印所有栈帧
调用栈中有两个贱帧，#0和#1，其中0号是当前帧swap函数，1号是其“上一个”栈帧--main函数。
(gdb) p a//在当前帧中查看a变量的值
(gdb) p b//在当前帧中查看b变量的值
(gdb) up//选择上一个栈帧。
(gdb) p a//查看变量a的值。
(gdb) p b//查看变量b的值。

取地址符号“&”和解引号符号“*”

在C/C++中变量都是放在内存中的，而内存中的每个字节都有一个称为地址（address）的编号。每个变量都占有一定数目的字节（可以用sizeof运算符获得），其中第一个字节的地址称为变量的地址。

int b=1;
int *a;//变量a是指向int型变量的指针。
a = &b;//把变量b的地址存放在指针a中。
*a = *a+3;//指针a指向的变量的值增加3;
*a=*a+1//也可以写成(*a)++,但不能写成*a++,因为++的优先级高于解引用运算符（取内容）。

关于指针初学者易犯的两个错误

//第一种错误写法
#include<iostream>
using namespace std;
void swap(int *a,int *b){
  int *t = a;
  a=b;
  b=t;
  //上述代码交换了局部变量a和b，但始终没有修改它们指向的内容。
}

int main(){
  int a=3,b=4;
  swap(&a,&b);
  cout<<a<<" "<<b;
}

//第二种错误写法
#include<iostream>
using namespace std;
void swap(int *a,int *b){
  int *t;
  *t=*a;*a=*b;*b=*t;
}
int main(){
  int a=3,b=4;
  swap(&a,&b);
  cout<<a<<" "<<b;
}

正确的写法如下：
```C++
#include<iostream>
using namespace std;
void swapa(int *a,int *b){
  int t;
  t=*a;
  *a=*b;
}
int main(){
  int a=3,b=4;
  swapa(&a,&b);
  cout<<a<<" "<<b;
  return 0;
}

数组作为函数的参数与返回值

以数组作为参数调用函数时，实上只有数组的首地址传给了函数，需要另加一个参数表示元素的个数。除了把数组首地址本身作为实参外，还可以利用指针的加减法把其它的元素的首地址传递给函数。

把函数作为函数的参数

比如sort函数的使用。

递归

递归定义

（1）1是正整数 （2）如果n是正整数，n+1也是正整数。 （3）只有通过(1)(2)定义出来的才是正整数。

f(0)=1; f(n)=n*f(n-1) (n>=1)

递归调用

函数可以直接或者间接调用自已，但要注意为递归函数编写终止条件，否则将产生无限递归。 例如：

#include<iostream>
using namespace std;
int f(int n){
  return n==0?1:n*f(n-1);
}

可以用gbd查看详细调用栈的信息。 每次递归调用都要往调用栈中增加一个栈帧，保存函数的调用关系和局部变量。调用层数很深的情况下，容易栈溢。常见的引起栈溢出的因素除了操作系统外，还有递归的深度和局部变量所点的空间大小。

这就是为什么我们在定义数组时，建议“把较大的数组放在main函数外”。所以栈溢出不一定是递归调用层数太深，也可能是局部变量太大。