递归

C允许函数调用它自己， 这种调用过程称为递归（recursion） 。

演示递归

main()调用了带参数1的up_and_down()函数， 执行结果是up_and_down()中的形式参数n的值是1， 所以打印语句#1打印Level 1。

假设有一条函数调用链——fun1()调用fun2()、 fun2()调用 fun3()、 fun3()调用fun4()。 当 fun4()结束时， 控制传回fun3()； 当fun3()结束时， 控制传回 fun2()； 当fun2()结束时， 控制传回fun1()。 递归的情况与此类似， 只不过fun1()、 fun2()、 fun3()和fun4()都是相同的函数。

递归的基础原理

第1， 每级函数调用都有自己的变量。 也就是说， 第1级的n和第2级的n不同， 所以程序创建了4个单独的变量， 每个变量名都是n， 但是它们的值各不相同。 当程序最终返回 up_and_down()的第1 级调用时， 最初的n仍然是它的初值1。

每次函数调用都会返回一次。 当函数执行完毕后， 控制权将被传回上一级递归。 程序必须按顺序逐级返回递归， 从某级up_and_down()返回上一级的up_and_down()， 不能跳级回到main()中的第1级调用。

递归函数中位于递归调用之前的语句， 均按被调函数的顺序执行。

递归函数中位于递归调用之后的语句， 均按被调函数相反的顺序执行。

虽然每级递归都有自己的变量， 但是并没有拷贝函数的代码。 程序按顺序执行函数中的代码， 而递归调用就相当于又从头开始执行函数的代码。 除了为每次递归调用创建变量外， 递归调用非常类似于一个循环语句。实际上， 递归有时可用循环来代替， 循环有时也能用递归来代替。

递归函数必须包含能让递归调用停止的语句。

尾递归

递归形式是把递归调用置于函数的末尾， 即正好在 return 语句之前。 这种形式的递归被称为尾递归（tail recursion） ， 因为递归调用在函数的末尾。 尾递归是最简单的递归形式， 因为它相当于循环。

使用循环的函数把ans初始化为1， 然后把ans与从n~2的所有递减整数相乘。 根据阶乘的公式， 还应该乘以1， 但是这并不会改变结果。

rfact()的递归调用不是函数的最后一行， 但是当n>0时， 它是该函数执行的最后一条语句， 因此它也是尾递归。

每次递归都会创建一组变量， 所以递归使用的内存更多， 而且每次递归调用都会把创建的一组新变量放在栈中。 递归调用的数量受限于内存空间。

递归和倒序计算

递归在处理倒序时非常方便。编写一个函数， 打印一个整数的二进制数。 二进制表示法根据 2 的幂来表示数字。 例如， 十进制数 234 实际上是2×102+3×101+4×100， 所以二进制数101实际上是1×22+0×21+1×20。 二进制数由0和1表示。

以二进制形式表示整数的方法或算法（algorithm） 在二进制中， 奇数的末尾一定是1， 偶数的末尾一定是0， 所以通过5 % 2即可确定5的二进制数的最后一位是1还是0。

递归的优缺点

递归既有优点也有缺点。 优点是递归为某些编程问题提供了最简单的解决方案。 缺点是一些递归算法会快速消耗计算机的内存资源。 另外， 递归不方便阅读和维护。

在程序中使用递归要特别注意， 尤其是效率优先的程序。

所有的C函数皆平等程序中的每个C函数与其他函数都是平等的。 每个函数都可以调用其他函数， 或被其他函数调用。

main()的确有点特殊。 当main()与程序中的其他函数放在一起时， 最开始执行的是main()函数中的第1条语句， 但是这也是局限之处。 main()也可以被自己或其他函数递归调用。

编译多源代码文件的程序

UNIX

UNIX系统中安装了UNIX C编译器cc（最初的cc已经停用， 但是许多UNIX系统都给cc命令起了一个别名用作其他编译器命令， 典型的是gcc或clang） 。

UNIX系统的make命令可自动管理多文件程序。

OS X的Terminal工具可以打开UNIX命令行环境， 但是必须先下载命令行编译器（GCC和Clang） 。

DOS命令行编译器

绝大多数DOS命令行编译器的工作原理和UNIX的cc命令类似， 只不过使用不同的名称而已。 其中一个区别是， 对象文件的扩展名是.obj， 而不是.o。 一些编译器生成的不是目标代码文件， 而是汇编语言或其他特殊代码的中间文件。

使用头文件

如果把main()放在第1个文件中， 把函数定义放在第2个文件中， 那么第1个文件仍然要使用函数原型。 把函数原型放在头文件中， 就不用在每次使用函数文件时都写出函数的原型。

程序中经常用C预处理器定义符号常量。 这种定义只储存了那些包含#define指令的文件。 如果把程序的一个函数放进一个独立的文件中，也可以使用#define指令访问每个文件。

查找地址：&运算符

指针（pointer） 是 C 语言最重要的（有时也是最复杂的） 概念之一， 用于储存变量的地址。 前面使用的scanf()函数中就使用地址作为参数。如果主调函数不使用return返回的值， 则必须通过地址才能修改主调函数中的值。

一元&运算符给出变量的存储地址。 如果pooh是变量名， 那么&pooh是变量的地址。 可以把地址看作是变量在内存中的位置。

首先， 两个pooh的地址不同， 两个bah的地址也不同。

函数调用mikado(pooh)把实际参数（main()中的pooh） 的值（2） 传递给形式参数（mikado()中的bah） 。 注意， 这种传递只传递了值。 涉及的两个变量（main()中的pooh和mikado()中的bah） 并未改变。

更改主调函数中的变量

interchange()， 它交换了 u 和 v 的值。 问题出在把结果传回 main()时。 interchange()使用的变量并不是main()中的变量。

指针简介

指针（pointer） 是一个值为内存地址的变量（或数据对象） 。 正如char类型变量的值是字符， int类型变量的值是整数， 指针变量的值是地址。

ptr = &pooh; // 把pooh的地址赋给ptr

ptr“指向”pooh。 ptr和&pooh的区别是ptr是变量，而&pooh是常量。 或者， ptr是可修改的左值， 而&pooh是右值。

ptr = &bah; // 把ptr指向bah， 而不是pooh

现在ptr的值是bah的地址。要创建指针变量， 先要声明指针变量的类型。 假设想把ptr声明为储存int类型变量地址的指针， 就要使用下面介绍的新运算符。

间接运算符: *

ptr = &bah;

然后使用间接运算符*（indirection operator） 找出储存在bah中的值， 该运算符有时也称为解引用运算符（dereferencing operator） 。 不要把间接运算符和二元乘法运算符（*） 混淆， 虽然它们使用的符号相同， 但语法功能不同。

val = *ptr; // 找出ptr指向的值

val = bah;

小结： 与指针相关的运算符

地址运算符： &

一般注解：

后跟一个变量名时， &给出该变量的地址。

声明指针

pointer ptr; // 不能这样声明指针

声明指针变量时必须指定指针所指向变量的类型， 因为不同的变量类型占用不同的存储空间， 一些指针操作要求知道操作对象的大小。程序必须知道储存在指定地址上的数据类型。 long和float可能占用相同的存储空间， 但是它们储存数字却大相径庭。

int * pi; // pi是指向int类型变量的指针

char * pc; // pc是指向char类型变量的指针

float * pf, * pg; // pf、 pg都是指向float类型变量的指针

类型说明符表明了指针所指向对象的类型， 星号（*） 表明声明的变量是一个指针。 int * pi;声明的意思是pi是一个指针， *pi是int类型

*和指针名之间的空格可有可无。 通常， 程序员在声明时使用空格， 在解引用变量时省略空格。

pc指向的值（*pc） 是char类型。pc是“指向char类型的指针”。 pc 的值是一个地址， 在大部分系统内部， 该地址由一个无符号整数表示。

使用指针在函数间通信

interchange(&x, &y);

该函数传递的不是x和y的值， 而是它们的地址。interchange()原型和定义中的形式参数u和v将把地址作为它们的值。

void interchange (int * u, int * v)

在函数体中声明了一个交换值时必需的临时变量

int temp;

把x的值储存在temp中temp = *u;

当程序要把一个值读入变量时（如本例中的num） ，调用的是scanf("%d", &num)。 scanf()读取一个值， 然后把该值储存到指定的地址上

变量的名称、 地址和变量的值之间关系密切。变量有两个属性： 名称和值

在 C 中， 可以通过&运算符访问地址， 通过*运算符获得地址上的值。printf("%d\n",barn)打印barn的值， 使用*运算符即可获得储存在地址上的值。 如果pbarn=&barn;， 那么*pbarn表示的是储存在&barn地址上的值。

普通变量把值作为基本量， 把地址作为通过&运算符获得的派生量， 而指针变量把地址作为基本量， 把值作为通过*运算符获得的派生量。

小结： 函数

形式：

典型的ANSI C函数的定义形式为：

返回类型 名称（形参声明列表）

函数体

形参声明列表是用逗号分隔的一系列变量声明。 除形参变量外， 函数的其他变量均在函数体的花括号之内声明。

传递值

实参用于把值从主调函数传递给被调函数。

函数的返回类型

函数的返回类型指的是函数返回值的类型。 如果返回值的类型与声明的返回类型不匹配， 返回值将被转换成函数声明的返回类型。

函数签名

函数的返回类型和形参列表构成了函数签名。 因此， 函数签名指定了传入函数的值的类型和函数返回值的类型。

关键概念

函数是如何把信息从一个函数传递到另一函数，也就是说， 要理解函数参数和返回值的工作原理。 另外， 要明白函数形参和其他局部变量都属于函数私有， 因此， 声明在不同函数中的同名变量是完全不同的变量。 而且， 函数无法直接访问其他函数中的变量。 这种限制访问保护了数据的完整性。 但是， 当确实需要在函数中访问另一个函数的数据时，可以把指针作为函数的参数。

本章小结

函数可以作为组成大型程序的构件块。 每个函数都应该有一个单独且定义好的功能。 使用参数把值传给函数， 使用关键字return把值返回函数。 如果函数返回的值不是int类型， 则必须在函数定义和函数原型中指定函数的类型。 如果需要在被调函数中修改主调函数的变量， 使用地址或指针作为参数。

ANSI C提供了一个强大的工具——函数原型， 允许编译器验证函数调用中使用的参数个数和类型是否正确。

C 函数可以调用本身， 这种调用方式被称为递归。 一些编程问题要用递归来解决， 但是递归不仅消耗内存多， 效率不高， 而且费时。