1
七、函数的调用机制八、函数的嵌套与递归九、数组的排序和查找
2
七、函数的调用机制函数的调用是通过称之为堆栈的结构进行的，堆栈是一种先进后出的动态内存空间，主要由计算机 CPU中的堆栈指针寄存器 ESP，堆栈段寄存器 SS，基址指针寄存器 EBP直接进行控制,ESP寄存器用来指示栈顶的偏移地址,SS段寄存器用于定位堆栈的段地址,EBP用于动态跟踪堆栈中的数据信息。
C/C++根据函数的定义既函数体中的执行语句建立相应的函数代码，函数代码被加载到内存的代码区，函数名代表了函数代码区的入口地址。将这一入口地址装入代码段寄存器 CS与指令指针寄存器 EIP，程序就进入函数的控制之中。
这一过程通过函数调用完成。
3
函数体中定义的变量称为局部变量，安排在堆栈空间。
函数的形参提供了与调用段的数据联系，函数调用之前实参表达式完成所有的副作用和求值计算。
C/C++语言没有规定实参表达式求值计算的次序，编译器可以以任意的次序完成实参表达式的初始化处理，如果存在重复的实参计算可适当引入临时变量事先进行优化。
一般编译器根据从右到左的顺序将参数表中的元素压入堆栈空间，即把右边第一个实参的值压入堆栈空间，接着把右边第二个实参的值压入堆栈空间，依此类推。
4
因此编译器从右到左的次序计算实参表达式的值，这不是语言的规定，而是大量编译器的具体选择。
函数的代码在没有激活时处于相对静态的状况，函数的形参个数、形参类型与形参的位置与函数体中涉及的局部变量确定函数堆栈空间的结构，堆栈空间仅在函数被调用才建立，调用结束堆栈空间占有的内存随即被释放。
形参中设置的缺省值是为实参预留的默认值，形参的数据状态期望实际参数的匹配而具体化。
5
虚实结合的过程相当于给相应形参赋初值的过程。函数调用时包含下面几个步骤：
a.根据函数的定义动态地建立函数的堆栈结构。
b,保存下一条指令的地址即返回地址。
c,虚实结合或具体地实参从右到左入栈。
d,进入被调函数的入口地址，执行被调函数。
e,被调函数由 return 语句返回到主控函数，释放堆栈空间占有的内存。
6
考虑下面示意性的代码：
type function(type0 t,type1& r,type2 *p)
{ type temp;
return temp;
}
void main (void)
{ type0 ta;
type1 ra;
type2 array[7 ];
type tta= function (ta,ra,array);
}
7
类型 type0,type1,type2可以是基本数据类型，如,
int,double等，也可以是用户自定义的类型 ;在函数 function
中定义了三个形参，第一个形参 t 为 type0型的变量，第二个形参 r 为 type1&类型的引用,第三个形参 p为 type2 *类型的指针。主控函数用语句：
tta=function(ta,ra,array);
函数体中引入的局部变量参数 1 t=ta 占 sizeof(type0)个字节参数 2 &r==&ra 占 sizeof(type1&)=2 or 4个字节参数 3 a= array 占 sizeof(type2*)=2 or 4个字节返回地址 CS:EIP栈底栈底堆栈向低地址增长
8
调用被调函数 function，第二个实参 ra 为 type1类型的变量,第二个形参 r 为 type1&类型的引用,C++根据引用使用相关变量的地址属性的规则，虚实结合的时候作为形参的引用 r取得相应实参 ra的地址。在被调函数体中对引用 r的改变就是对变量 ra值的改变。
函数的返回一般用 return语句完成，系统根据返回的调用约定采用不同的返回机制。
对于传值返回,
若返回值的数据长度不超过 4字节，结果可以通过 EAX
寄存器转送给调用段的变量 ;
若返回值的数据长度不超过 8字节，结果可以通过
EDX,EAX寄存器转送给调用段的变量 ;
9
若返回值的数据长度 sizeof(type)超过 8字节,将返回结果存放在临时空间中，此时系统建立一个临时结构变量或临时对象。
调用结束系统会尽早释放临时结构变量或临时对象占有的内存空间。
对于引用返回，系统将返回的引用直接放置在向关变量的地址空间单元中，因而省去了建立临时变量或临时对象这一过程。
除非返回的时候涉及到类型的强制转换，从表达式的类型到函数的返回类型如果存在类型转换，会导致临时对象的创建。
10
八、函数的嵌套与递归
C/C++语言允许在一个函数中调用另一个函数，在一个函数中调用其它函数的现象称为函数的嵌套。
C/C++语言对于嵌套的层次没有加以限制，其层数称为嵌套深度。
如果在 main函数中调用了 funct1函数，在 funct1函数中调用了 funct2函数,.,functn_1函数中调用了 functn函数，则可以说函数的嵌套深度为 n。
函数的多层嵌套中形成函数调用与被调用关系，被调函数是被主控函数调用的函数。 例如：
funct2的主控函数是 funct1函数,funct1的被调函数是
funct2函数。
11
函数在各级嵌套调用中愈是上层的主控函数中的局部变量相对于下层的被调函数中的局部变量具有愈长的寿命，
但维持其相应的局域可访问性。
在函数嵌套调用的情况下，如果在嵌套的层次体系中追根逆源时导致函数对自身的调用，这样的现象称为函数的递归调用。
12
递归调用分两种情况：
一种是直接递归，另一种是间接递归。
直接递归调用就是在 funct函数体中调用 funct函数，
funct既是主控函数又是被调函数。
间接递归则是函数嵌套调用时如 funct1调用
functk....functk调用 functm...functm调用 funct1，形成函数调用的一个循环链，因此递归调用时必须保证循环链的中断条件。
C/C++语言中递归函数常对应数学上函数的递归定义。
13
[例 ] 用递归方法求 n阶乘 n!
n!的递归定义为：
0！ =1
n!=n*(n-1)! (n>0)
[例 ] 嵌套与递归的比较
#include<stdio.h>
long fac1(long n) { return 1; }
long fac2(long n) { return n*fac1(n-1); }
long fac3(long n) { return n*fac2(n-1); }
long fac4(long n) { return n*fac3(n-1); }
long facn(long n)
//注意 facn实现了 (n>0)条件
14
{ if (n>0) return n*facn(n-1);
else return 1;
} //首先判断 if(n>0) 然后递归调用是关键的
void main (void)
{ printf (" embedding 3!=%d,recursion 3!=%d\t",
fac3(3),facn(3));
printf (" embedding 4!=%d,recursion 4!=%d\n",
fac4(4),facn(4));
}
//输出,embedding 3!=6,recursion 3!=6
embedding 4!=24,recursion 4!=24
15
递归调用的过程实际上是函数反复嵌套调用自身的过程，下面展开 n阶乘递归调用函数当 n等于 4的自嵌套调用步骤：
a,递归阶段 (recursive step)
第一次函数调用 facn(4)时在函数体中通过直接的 return
语句返回 4*facn(3)，进行了第二次函数调用 facn(3);
函数调用 facn(3)进入函数中导致进入 if分支，此时 return
语句返回 3*facn(2)，引发第三次函数调用 facn(2);
函数调用 facn(2)进入函数中导致进入 if分支，此时 return
语句返回 2*facn(1)，引发第四次函数调用 facn(1);
函数调用 facn(1)进入函数中导致进入 if分支，此时 return
语句返回 1*facn(0)，引发第五次函数调用 facn(0)=1。
16
b,递归结束条件函数调用 facn(0)进入函数体的 else分支此时返回 1，递归函数不再嵌套调用自身,递归过程完结。因此函数调用的结果为,4*3*2*1*1=24
上面递归的过程如果分解为函数名不同但计算实质一样的若干函数则调用中参量的传递关系要明朗些，由此形成不同函数的嵌套调用。
递归调用是嵌套调用的特例,但递归浓缩了相似函数重复嵌套的逻辑组织。
17
在定义递归函数时应该先判断然后才进入递归调用。函数的递归调用应保证递归的终止条件，结束函数的无穷递归。 例如,void f (int n) { f (n-1);}是无穷递归。
函数嵌套调用中需要经过形参入栈、主控函数中调用点之后的返回地址保存、切入被调函数的入口地址、进入被调函数的代码、堆栈恢复和返回主控函数的过程。
函数递归调用时先入栈的形式参数在堆栈内存空间的深部，本身作为下次递归调用的初始实参，在下一回合递归调用时的形参位于堆栈空间的浅部。
由于数值传递形参入口的单向安全性，原先的实参变量不受后面调用的影响。
18
[例 ] 递归和嵌套计算数组的和
#include<stdio.h>
long rsum (long *p,int n)
{ if (n>0) return rsum(p,n-1)+p[n-1];
else return 0;
//递归结束条件，递归函数的结果一般并不简单地等于 0
} // rsum(p,n)计算的结果相当于
//p[n-1]+ p[n-2]+,..+p[1]+ p[0]+0= rsum(p,n)
long sum0 (long *p,int n=0) { return 0;}
long sum1(long *p,int n=1) { return sum0(p,n-1)+p[n-1];}
long sum2(long *p,int n=2) { return sum1(p,n-1)+p[n-1];}
long sum3(long *p,int n=3) { return sum2(p,n-1)+p[n-1];}
19
void main (void)
// sum3(p,n)计算的结果相当于 p[n-1]+ p[n-2]+ p[n-3]+ (p[n-4]=0)
{ long a[ ]={1,2,3,4,5,6,7,8,9,10};
printf ("1+2+3 =%d,sum=%d\t",sum3(a,3),rsum(a,3));
printf ("4+5+6=%d,sum=%d\t",sum3(a+3),rsum(a+3,3));
printf ("7+8+9=%d,sum=%d\n",sum3(a,9),rsum(a,9));
}
// 输出,
1+2+3=6,sum=6 4+5+6 =15,sum=15 7+8+9=24,sum=45
20
[例 ] 递归显示字符串。 f1顺序显示指针数组的字符串,f2逆序显示。
# include<stdio.h>
char* s[]={ "a","bb","ccc","dddd",0 };
//定义全局指针数组,0作为结束标志
void f2(char* *p)
{ if(*p!=0) f2(p+1),printf ("%s;",*p); }
//*p!=0作为过滤条件
void f1(char* p[ ])
{ if(*p!=0) printf("%s;",*p),f1(p+1);}
// *p==0不进入递归调用
void main() { f1(s); f2(s); }
//输出,a; bb; ccc;dddd;dddd;ccc;bb;a;
21
[例 ] 间接递归交错地显示字符数组的字符
# include<stdio.h>
char s[ ]="abcd"; //定义全局字符数组,0作为结束标志
void f1 (char p[ ]);
//逗号表达式语句作为 if分支的执行语句
void f2 (char *p)
{ if (*p!=0) f1(p+1),printf ("%c",*p); }
//*p!=0作为过滤条件
void f1(char p[ ])
{ if(*p!=0) printf ("%c",*p),f2(p+1);}
void main() { f1(s); f2(s); } //输出,acdbbdca
22
递归的两面观：
原则上任何递归算法可以用循环结构等价的实现，迭代循环运行效率高稳定性强程序的容错性能优越，因此优先使用迭代循环以保证程序的可靠性。
递归深度越大，递归函数在递归调用中需要建立的堆栈空间资源越多，因此递归函数容易导致堆栈空间溢出程序在运行时出现故障；
特别地递归深度取决于入口参数，是运行时动态确定的，存在运行时递而不归的现象。
23
递归函数既是主控函数又是被调函数，递归函数的代码驻留唯一的一个版本在内存中，递归调用过程中需要在递归函数唯一的代码段、该代码涉及到的数据段和保留其间往返信息的堆栈空间来回切换，因此递归在空间上占用更多的堆栈内存，在函数调用的往返上耗费多余的时间。
递归的好处在于可以简化程序的设计。
对于函数的递归定义用 C/C++语言中的函数递归实现比较容易完成。
24
九、数组的排序和查找
1.直接插入排序设内存空间的值根据从小到大的次序排列,即增序排列 ;
直接插入排序是将后面小的元素直接插入到数组的前面,无序区之前到待插入点之间的元素依次后移。
基本思路为：
a,初始状态是等待排序的内存空间的数据集合,最简单的数据集合为数组
25
b.中间状态分为两个部分,一部分是排序好的有序区,另一部分为未排序的无序区。设有序区在前面，无序区在后面。这样数据集合的内存空间表示为：
[有序区 ]（无序区）
初始状态对应的区域认为第一个元素处于有序区,其余是无序区，排好序号的最终状态都是有序区。排序的过程是有序区增加无序区减少的过程。
c,基本操作是从无序区取第一个元素，根据关键值大小插入到有序区的适当位置，维持有序区的既定排列次序。
26
对应无序区的第一个元素，示意如下,
初始状态 [。 ](? 。 。 。 。 。 。 。 。 )
插入前 [。 。 。 。 。 ]（? 。 。 。 。）
插入点插入后 [。 。 。 。 。 ]( 。 。 。 。）
初始状态 5 4 3 1 2 6 7
1.选 4前插 4 5 3 1 2 6 7
2.选 3前插 3 4 5 1 2 6 7
3.选 1前插 1 3 4 5 2 6 7
4.选 2前插 1 2 3 4 5 6 7
27
# include<stdio.h>
void show (long * a,int i,int n)
{ printf ("%d ",i);
for (int k=0; k<n;k++) printf ("%d\t ",a[k]);
printf ("\n"); }
void InsertSort (long a[ ],int n)
{ for (int i=1; i<n; i++)
{ show (a,i,n); long temp=a[i]; int j=i;
for( ; temp<a[j-1]; j--) a[j]=a[j-1];
a[j]=temp; } }
void main(void)
{ long a[7]={5,4,3,1,2,6,7};
InsertSort(a,7); show(a,7,7);
}
28
2,选择排序选择排序的思路是,
a.初始状态,
等待排序的数组分为有序区和无序区,初始有序区认为是空 ;
b.基本操作,
从整个无序区选择关键值最小的元素,将其添补到有序区的尾部,
c.排序过程,
从初始状态无序区为最大不断执行基本操作,直到无序区变为空,
29
初始状态 ( 。 。 。 。 。 。 。 。 )
第一次排序后最小元素在第一个位置 [。 ]（ 。 。 。 。 。 。。 。）
第二次排序后次小元素在第二个位置 [。 ] [。 ]（ 。 。 。 。 。 。。 。）
基本操作 [。 。 。 。 。 ]（ 。 。。 。）
插入到尾部原始次序 50 40 30 10 20 60 70
1.选出最小元素 10 10 40 30 50 20 60 70
2.选出最小元素 20 10 20 30 50 40 60 70
10 20 30 50 40 60 70
3.选出最小元素 40 10 20 30 40 50 60 70
30
void swap (int &x,int &y) { int t=x; x=y; y=t;}
void SelectSort (int a[ ],int n)
{ for (int i=0;i<n-1;i++)
{
int min=i;
for (int j=i+1; j<n; j++)
if (a[j]<a[min])
min=j;
if (min!=i)
swap (a[i],a[min]);
}
}
31
3,交换法实现冒泡排序交换排序的基本思想是两两比较数组中的元素，及时交换不满足次序的各对元素，直到全部满足顺序为止，冒泡排序属于交换排序。
按照升序排列的冒泡算法总的思路为：大的元素下落或往后移、小的元素上升或前移。
冒泡排序由于循环的扫描方向不同而存在略微不同的交换过程。一种是大的元素优先降落，一种是小的元素优先上升。
32
void swap(int &x,int &y) { int t=x; x=y; y=t;}
void BubbleSortB (int a[ ],int n)
{ for (int i=1; i<n; i++)
for (int j=0;j<n-i;j++)
if (a[j]>a[j+1])
swap(a[j],a[j+1]);
}
void BubbleSortS(int a[],int n)
{ for (int i=0;i<n-1;i++)
for (int j=n-1;j>i;j--)
if (a[j-1]>a[j])
swap (a[j-1],a[j]);
}
33
void main(void) void main(void)
{ int a[7]={4,6,1,5,2,3,0}; { int a[7]={4,6,1,5,2,3,0};
BubbleSortS (a,7); BubbleSortB (a,7);
} }
小元素优先上升 大的元素优先降落
BubbleSortS计算如下,BubbleSortB的中间结果如下,
0,4 6 1 5 2 3 0 0,4 6 1 5 2 3 0
1,0 4 6 1 5 2 3 1,4 1 5 2 3 0 6
2,0 1 4 6 2 5 3 2,1 4 2 3 0 5 6
3,0 1 2 4 6 3 5 3,1 2 3 0 4 5 6
4,0 1 2 3 4 6 5 4,1 2 0 3 4 5 6
5,0 1 2 3 4 5 6 5,1 0 2 3 4 5 6
8,0 1 2 3 4 5 6 8,0 1 2 3 4 5 6
34
4,二分查找二分法搜寻的编程思路为：将要搜寻的空间一分为二，然后判断要找的元素落入那一个子空间，进一步等分隔半的子空间，如此细分直到找到为止或一无所获。二分法求方程的根与下面二分法在数组中查找特定值的元素都是基于一分为二逐步逼近的想法。
low
mid high
mid=(low+high)/2 x
low
mid
high low mid high low
mid
high low mid mid
x high
high=mid-1 low=mid+1
x<a[mid]搜寻前半部分 x>a[mid] 搜寻后半部分二分搜寻示意图
35
[例 ] 三路分支确定二分查找函数的流程
#include <stdio.h>
int BinSearch (int a[],int low,int high,int x)
{ int mid;
while (low<=high)
{ mid=(low+high)/2;
if (x<a[mid]) high=mid-1;
else if (x>a[mid]) low=mid+1;
else return mid;
}
return -1;
}
36
void main()
{ int a[ ]= {2,4,6,8,10,12,12,14,18};
const int n=sizeof (a)/sizeof (a[0]);
int s= BinSearch (a,0,n-1,6);
int f = BinSearch (a,1,n-1,18);
printf ("s=%d,f=%d\n",s,f);
}
//程序运行输出结果,s=2,f=8
37
七、函数的调用机制八、函数的嵌套与递归九、数组的排序和查找
2
七、函数的调用机制函数的调用是通过称之为堆栈的结构进行的，堆栈是一种先进后出的动态内存空间，主要由计算机 CPU中的堆栈指针寄存器 ESP，堆栈段寄存器 SS，基址指针寄存器 EBP直接进行控制,ESP寄存器用来指示栈顶的偏移地址,SS段寄存器用于定位堆栈的段地址,EBP用于动态跟踪堆栈中的数据信息。
C/C++根据函数的定义既函数体中的执行语句建立相应的函数代码，函数代码被加载到内存的代码区，函数名代表了函数代码区的入口地址。将这一入口地址装入代码段寄存器 CS与指令指针寄存器 EIP，程序就进入函数的控制之中。
这一过程通过函数调用完成。
3
函数体中定义的变量称为局部变量，安排在堆栈空间。
函数的形参提供了与调用段的数据联系，函数调用之前实参表达式完成所有的副作用和求值计算。
C/C++语言没有规定实参表达式求值计算的次序，编译器可以以任意的次序完成实参表达式的初始化处理，如果存在重复的实参计算可适当引入临时变量事先进行优化。
一般编译器根据从右到左的顺序将参数表中的元素压入堆栈空间，即把右边第一个实参的值压入堆栈空间，接着把右边第二个实参的值压入堆栈空间，依此类推。
4
因此编译器从右到左的次序计算实参表达式的值，这不是语言的规定，而是大量编译器的具体选择。
函数的代码在没有激活时处于相对静态的状况，函数的形参个数、形参类型与形参的位置与函数体中涉及的局部变量确定函数堆栈空间的结构，堆栈空间仅在函数被调用才建立，调用结束堆栈空间占有的内存随即被释放。
形参中设置的缺省值是为实参预留的默认值，形参的数据状态期望实际参数的匹配而具体化。
5
虚实结合的过程相当于给相应形参赋初值的过程。函数调用时包含下面几个步骤：
a.根据函数的定义动态地建立函数的堆栈结构。
b,保存下一条指令的地址即返回地址。
c,虚实结合或具体地实参从右到左入栈。
d,进入被调函数的入口地址，执行被调函数。
e,被调函数由 return 语句返回到主控函数，释放堆栈空间占有的内存。
6
考虑下面示意性的代码：
type function(type0 t,type1& r,type2 *p)
{ type temp;
return temp;
}
void main (void)
{ type0 ta;
type1 ra;
type2 array[7 ];
type tta= function (ta,ra,array);
}
7
类型 type0,type1,type2可以是基本数据类型，如,
int,double等，也可以是用户自定义的类型 ;在函数 function
中定义了三个形参，第一个形参 t 为 type0型的变量，第二个形参 r 为 type1&类型的引用,第三个形参 p为 type2 *类型的指针。主控函数用语句：
tta=function(ta,ra,array);
函数体中引入的局部变量参数 1 t=ta 占 sizeof(type0)个字节参数 2 &r==&ra 占 sizeof(type1&)=2 or 4个字节参数 3 a= array 占 sizeof(type2*)=2 or 4个字节返回地址 CS:EIP栈底栈底堆栈向低地址增长
8
调用被调函数 function，第二个实参 ra 为 type1类型的变量,第二个形参 r 为 type1&类型的引用,C++根据引用使用相关变量的地址属性的规则，虚实结合的时候作为形参的引用 r取得相应实参 ra的地址。在被调函数体中对引用 r的改变就是对变量 ra值的改变。
函数的返回一般用 return语句完成，系统根据返回的调用约定采用不同的返回机制。
对于传值返回,
若返回值的数据长度不超过 4字节，结果可以通过 EAX
寄存器转送给调用段的变量 ;
若返回值的数据长度不超过 8字节，结果可以通过
EDX,EAX寄存器转送给调用段的变量 ;
9
若返回值的数据长度 sizeof(type)超过 8字节,将返回结果存放在临时空间中，此时系统建立一个临时结构变量或临时对象。
调用结束系统会尽早释放临时结构变量或临时对象占有的内存空间。
对于引用返回，系统将返回的引用直接放置在向关变量的地址空间单元中，因而省去了建立临时变量或临时对象这一过程。
除非返回的时候涉及到类型的强制转换，从表达式的类型到函数的返回类型如果存在类型转换，会导致临时对象的创建。
10
八、函数的嵌套与递归
C/C++语言允许在一个函数中调用另一个函数，在一个函数中调用其它函数的现象称为函数的嵌套。
C/C++语言对于嵌套的层次没有加以限制，其层数称为嵌套深度。
如果在 main函数中调用了 funct1函数，在 funct1函数中调用了 funct2函数,.,functn_1函数中调用了 functn函数，则可以说函数的嵌套深度为 n。
函数的多层嵌套中形成函数调用与被调用关系，被调函数是被主控函数调用的函数。 例如：
funct2的主控函数是 funct1函数,funct1的被调函数是
funct2函数。
11
函数在各级嵌套调用中愈是上层的主控函数中的局部变量相对于下层的被调函数中的局部变量具有愈长的寿命，
但维持其相应的局域可访问性。
在函数嵌套调用的情况下，如果在嵌套的层次体系中追根逆源时导致函数对自身的调用，这样的现象称为函数的递归调用。
12
递归调用分两种情况：
一种是直接递归，另一种是间接递归。
直接递归调用就是在 funct函数体中调用 funct函数，
funct既是主控函数又是被调函数。
间接递归则是函数嵌套调用时如 funct1调用
functk....functk调用 functm...functm调用 funct1，形成函数调用的一个循环链，因此递归调用时必须保证循环链的中断条件。
C/C++语言中递归函数常对应数学上函数的递归定义。
13
[例 ] 用递归方法求 n阶乘 n!
n!的递归定义为：
0！ =1
n!=n*(n-1)! (n>0)
[例 ] 嵌套与递归的比较
#include<stdio.h>
long fac1(long n) { return 1; }
long fac2(long n) { return n*fac1(n-1); }
long fac3(long n) { return n*fac2(n-1); }
long fac4(long n) { return n*fac3(n-1); }
long facn(long n)
//注意 facn实现了 (n>0)条件
14
{ if (n>0) return n*facn(n-1);
else return 1;
} //首先判断 if(n>0) 然后递归调用是关键的
void main (void)
{ printf (" embedding 3!=%d,recursion 3!=%d\t",
fac3(3),facn(3));
printf (" embedding 4!=%d,recursion 4!=%d\n",
fac4(4),facn(4));
}
//输出,embedding 3!=6,recursion 3!=6
embedding 4!=24,recursion 4!=24
15
递归调用的过程实际上是函数反复嵌套调用自身的过程，下面展开 n阶乘递归调用函数当 n等于 4的自嵌套调用步骤：
a,递归阶段 (recursive step)
第一次函数调用 facn(4)时在函数体中通过直接的 return
语句返回 4*facn(3)，进行了第二次函数调用 facn(3);
函数调用 facn(3)进入函数中导致进入 if分支，此时 return
语句返回 3*facn(2)，引发第三次函数调用 facn(2);
函数调用 facn(2)进入函数中导致进入 if分支，此时 return
语句返回 2*facn(1)，引发第四次函数调用 facn(1);
函数调用 facn(1)进入函数中导致进入 if分支，此时 return
语句返回 1*facn(0)，引发第五次函数调用 facn(0)=1。
16
b,递归结束条件函数调用 facn(0)进入函数体的 else分支此时返回 1，递归函数不再嵌套调用自身,递归过程完结。因此函数调用的结果为,4*3*2*1*1=24
上面递归的过程如果分解为函数名不同但计算实质一样的若干函数则调用中参量的传递关系要明朗些，由此形成不同函数的嵌套调用。
递归调用是嵌套调用的特例,但递归浓缩了相似函数重复嵌套的逻辑组织。
17
在定义递归函数时应该先判断然后才进入递归调用。函数的递归调用应保证递归的终止条件，结束函数的无穷递归。 例如,void f (int n) { f (n-1);}是无穷递归。
函数嵌套调用中需要经过形参入栈、主控函数中调用点之后的返回地址保存、切入被调函数的入口地址、进入被调函数的代码、堆栈恢复和返回主控函数的过程。
函数递归调用时先入栈的形式参数在堆栈内存空间的深部，本身作为下次递归调用的初始实参，在下一回合递归调用时的形参位于堆栈空间的浅部。
由于数值传递形参入口的单向安全性，原先的实参变量不受后面调用的影响。
18
[例 ] 递归和嵌套计算数组的和
#include<stdio.h>
long rsum (long *p,int n)
{ if (n>0) return rsum(p,n-1)+p[n-1];
else return 0;
//递归结束条件，递归函数的结果一般并不简单地等于 0
} // rsum(p,n)计算的结果相当于
//p[n-1]+ p[n-2]+,..+p[1]+ p[0]+0= rsum(p,n)
long sum0 (long *p,int n=0) { return 0;}
long sum1(long *p,int n=1) { return sum0(p,n-1)+p[n-1];}
long sum2(long *p,int n=2) { return sum1(p,n-1)+p[n-1];}
long sum3(long *p,int n=3) { return sum2(p,n-1)+p[n-1];}
19
void main (void)
// sum3(p,n)计算的结果相当于 p[n-1]+ p[n-2]+ p[n-3]+ (p[n-4]=0)
{ long a[ ]={1,2,3,4,5,6,7,8,9,10};
printf ("1+2+3 =%d,sum=%d\t",sum3(a,3),rsum(a,3));
printf ("4+5+6=%d,sum=%d\t",sum3(a+3),rsum(a+3,3));
printf ("7+8+9=%d,sum=%d\n",sum3(a,9),rsum(a,9));
}
// 输出,
1+2+3=6,sum=6 4+5+6 =15,sum=15 7+8+9=24,sum=45
20
[例 ] 递归显示字符串。 f1顺序显示指针数组的字符串,f2逆序显示。
# include<stdio.h>
char* s[]={ "a","bb","ccc","dddd",0 };
//定义全局指针数组,0作为结束标志
void f2(char* *p)
{ if(*p!=0) f2(p+1),printf ("%s;",*p); }
//*p!=0作为过滤条件
void f1(char* p[ ])
{ if(*p!=0) printf("%s;",*p),f1(p+1);}
// *p==0不进入递归调用
void main() { f1(s); f2(s); }
//输出,a; bb; ccc;dddd;dddd;ccc;bb;a;
21
[例 ] 间接递归交错地显示字符数组的字符
# include<stdio.h>
char s[ ]="abcd"; //定义全局字符数组,0作为结束标志
void f1 (char p[ ]);
//逗号表达式语句作为 if分支的执行语句
void f2 (char *p)
{ if (*p!=0) f1(p+1),printf ("%c",*p); }
//*p!=0作为过滤条件
void f1(char p[ ])
{ if(*p!=0) printf ("%c",*p),f2(p+1);}
void main() { f1(s); f2(s); } //输出,acdbbdca
22
递归的两面观：
原则上任何递归算法可以用循环结构等价的实现，迭代循环运行效率高稳定性强程序的容错性能优越，因此优先使用迭代循环以保证程序的可靠性。
递归深度越大，递归函数在递归调用中需要建立的堆栈空间资源越多，因此递归函数容易导致堆栈空间溢出程序在运行时出现故障；
特别地递归深度取决于入口参数，是运行时动态确定的，存在运行时递而不归的现象。
23
递归函数既是主控函数又是被调函数，递归函数的代码驻留唯一的一个版本在内存中，递归调用过程中需要在递归函数唯一的代码段、该代码涉及到的数据段和保留其间往返信息的堆栈空间来回切换，因此递归在空间上占用更多的堆栈内存，在函数调用的往返上耗费多余的时间。
递归的好处在于可以简化程序的设计。
对于函数的递归定义用 C/C++语言中的函数递归实现比较容易完成。
24
九、数组的排序和查找
1.直接插入排序设内存空间的值根据从小到大的次序排列,即增序排列 ;
直接插入排序是将后面小的元素直接插入到数组的前面,无序区之前到待插入点之间的元素依次后移。
基本思路为：
a,初始状态是等待排序的内存空间的数据集合,最简单的数据集合为数组
25
b.中间状态分为两个部分,一部分是排序好的有序区,另一部分为未排序的无序区。设有序区在前面，无序区在后面。这样数据集合的内存空间表示为：
[有序区 ]（无序区）
初始状态对应的区域认为第一个元素处于有序区,其余是无序区，排好序号的最终状态都是有序区。排序的过程是有序区增加无序区减少的过程。
c,基本操作是从无序区取第一个元素，根据关键值大小插入到有序区的适当位置，维持有序区的既定排列次序。
26
对应无序区的第一个元素，示意如下,
初始状态 [。 ](? 。 。 。 。 。 。 。 。 )
插入前 [。 。 。 。 。 ]（? 。 。 。 。）
插入点插入后 [。 。 。 。 。 ]( 。 。 。 。）
初始状态 5 4 3 1 2 6 7
1.选 4前插 4 5 3 1 2 6 7
2.选 3前插 3 4 5 1 2 6 7
3.选 1前插 1 3 4 5 2 6 7
4.选 2前插 1 2 3 4 5 6 7
27
# include<stdio.h>
void show (long * a,int i,int n)
{ printf ("%d ",i);
for (int k=0; k<n;k++) printf ("%d\t ",a[k]);
printf ("\n"); }
void InsertSort (long a[ ],int n)
{ for (int i=1; i<n; i++)
{ show (a,i,n); long temp=a[i]; int j=i;
for( ; temp<a[j-1]; j--) a[j]=a[j-1];
a[j]=temp; } }
void main(void)
{ long a[7]={5,4,3,1,2,6,7};
InsertSort(a,7); show(a,7,7);
}
28
2,选择排序选择排序的思路是,
a.初始状态,
等待排序的数组分为有序区和无序区,初始有序区认为是空 ;
b.基本操作,
从整个无序区选择关键值最小的元素,将其添补到有序区的尾部,
c.排序过程,
从初始状态无序区为最大不断执行基本操作,直到无序区变为空,
29
初始状态 ( 。 。 。 。 。 。 。 。 )
第一次排序后最小元素在第一个位置 [。 ]（ 。 。 。 。 。 。。 。）
第二次排序后次小元素在第二个位置 [。 ] [。 ]（ 。 。 。 。 。 。。 。）
基本操作 [。 。 。 。 。 ]（ 。 。。 。）
插入到尾部原始次序 50 40 30 10 20 60 70
1.选出最小元素 10 10 40 30 50 20 60 70
2.选出最小元素 20 10 20 30 50 40 60 70
10 20 30 50 40 60 70
3.选出最小元素 40 10 20 30 40 50 60 70
30
void swap (int &x,int &y) { int t=x; x=y; y=t;}
void SelectSort (int a[ ],int n)
{ for (int i=0;i<n-1;i++)
{
int min=i;
for (int j=i+1; j<n; j++)
if (a[j]<a[min])
min=j;
if (min!=i)
swap (a[i],a[min]);
}
}
31
3,交换法实现冒泡排序交换排序的基本思想是两两比较数组中的元素，及时交换不满足次序的各对元素，直到全部满足顺序为止，冒泡排序属于交换排序。
按照升序排列的冒泡算法总的思路为：大的元素下落或往后移、小的元素上升或前移。
冒泡排序由于循环的扫描方向不同而存在略微不同的交换过程。一种是大的元素优先降落，一种是小的元素优先上升。
32
void swap(int &x,int &y) { int t=x; x=y; y=t;}
void BubbleSortB (int a[ ],int n)
{ for (int i=1; i<n; i++)
for (int j=0;j<n-i;j++)
if (a[j]>a[j+1])
swap(a[j],a[j+1]);
}
void BubbleSortS(int a[],int n)
{ for (int i=0;i<n-1;i++)
for (int j=n-1;j>i;j--)
if (a[j-1]>a[j])
swap (a[j-1],a[j]);
}
33
void main(void) void main(void)
{ int a[7]={4,6,1,5,2,3,0}; { int a[7]={4,6,1,5,2,3,0};
BubbleSortS (a,7); BubbleSortB (a,7);
} }
小元素优先上升 大的元素优先降落
BubbleSortS计算如下,BubbleSortB的中间结果如下,
0,4 6 1 5 2 3 0 0,4 6 1 5 2 3 0
1,0 4 6 1 5 2 3 1,4 1 5 2 3 0 6
2,0 1 4 6 2 5 3 2,1 4 2 3 0 5 6
3,0 1 2 4 6 3 5 3,1 2 3 0 4 5 6
4,0 1 2 3 4 6 5 4,1 2 0 3 4 5 6
5,0 1 2 3 4 5 6 5,1 0 2 3 4 5 6
8,0 1 2 3 4 5 6 8,0 1 2 3 4 5 6
34
4,二分查找二分法搜寻的编程思路为：将要搜寻的空间一分为二，然后判断要找的元素落入那一个子空间，进一步等分隔半的子空间，如此细分直到找到为止或一无所获。二分法求方程的根与下面二分法在数组中查找特定值的元素都是基于一分为二逐步逼近的想法。
low
mid high
mid=(low+high)/2 x
low
mid
high low mid high low
mid
high low mid mid
x high
high=mid-1 low=mid+1
x<a[mid]搜寻前半部分 x>a[mid] 搜寻后半部分二分搜寻示意图
35
[例 ] 三路分支确定二分查找函数的流程
#include <stdio.h>
int BinSearch (int a[],int low,int high,int x)
{ int mid;
while (low<=high)
{ mid=(low+high)/2;
if (x<a[mid]) high=mid-1;
else if (x>a[mid]) low=mid+1;
else return mid;
}
return -1;
}
36
void main()
{ int a[ ]= {2,4,6,8,10,12,12,14,18};
const int n=sizeof (a)/sizeof (a[0]);
int s= BinSearch (a,0,n-1,6);
int f = BinSearch (a,1,n-1,18);
printf ("s=%d,f=%d\n",s,f);
}
//程序运行输出结果,s=2,f=8
37
