函数（二）

紧接上文，我们把函数的基础语法结束了，本章将讲解到较为难一点的内容，譬如递归调用。

一：函数的嵌套调用和链式访问

函数与函数之间并不是独立存在的，函数和函数之间可以根据实际的需求进行组合的，也就是互相调用的。

嵌套调用

举例：

#include <stdio.h>
void new_line()
{
 printf("hehe\n");
}
void three_line()
{
    int i = 0;
 for(i=0; i<3; i++)
   {
        new_line();
   }
}
int main()
{
 three_line();
 return 0;
}

函数可以嵌套调用，但是不能嵌套定义。

链式访问

把一个函数的返回值作为另外一个函数的参数就叫做链式访问。

举例：

#include <stdio.h>
#include <string.h>
int main()
{
    char arr[20] = "hello";
 int ret = strlen(strcat(arr,"bit"));
 printf("%d\n", ret);
 return 0;
}

简单介绍一个strlen函数，它被包含在头文件<string.h>中,其作用的是求字符串的长度。

strlen和sizeof的比较：

strlen是一个库函数，在求字符串长度时不计算\0，只计算到\0之前的一个字符。

sizeof是一个操作符，它在求字符串长度时会计算\0。

例二：

#include <stdio.h>
int main()
{
    printf("%d", printf("%d", printf("%d", 43)));
    return 0; 
}

这些都叫做链式访问。

二：函数的声明和定义

函数的声明:

在之前写的函数代码中，很容易看见我们一般都是把函数写在main函数之前，因为我们的编译器在读取代码时都是以行行读取的。在我们的main函数读取到我们自定义函数时，如果自定义函数写在main之前，编译器不会报错；但是自定义函数在main之前，编译器很有可能弹出警报，函数未定义。

注意事项

1. 告诉编译器有一个函数叫什么，参数是什么，返回类型是什么。但是具体是不是存在，函数

声明决定不了。

2. 函数的声明一般出现在函数的使用之前。要满足 先声明后使用。

3. 函数的声明一般要放在头文件中的。

我们之前写的文件都是在同一个文件中的，那么在不同文件进行调用过程中需要进行引头文件，所以函数声明需要放在头文件中。

函数定义

函数的定义是指函数的具体实现，交待函数的功能实现。

test.h的内容

放置函数的声明

#ifndef __TEST_H__

#define __TEST_H__

//函数的声明

int Add(int x, int y);

#endif //__TEST_H__

test.c的内容

放置函数的实现

#include "test.h"

//函数Add的实现

int Add(int x, int y)

{

return x+y;

}

具体的等以后在来具体实例学习。

三:函数递归

什么是递归

程序调用自身的编程技巧称为递归（ recursion）。

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接

调用自身的

一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，

递归策略

只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

最终目的就是：大事化小，小事化了。

递归必须满足的两个必要条件：

1.存在限制条件，当满足这个限制条件的时候，递归便不再继续。

2.每次递归调用之后越来越接近这个限制条件。

如果不满足这个条件，递归有可能成为一个死递归，无限循环至程序崩溃。

举例说明：

接受一个整型值（无符号），按照顺序打印它的每一位。
例如：
输入：1234，输出 1 2 3 4


#include <stdio.h>
void print(int n) {
 if(n>9)
 {
 print(n/10);
 }
 printf("%d ", n%10);
}
int main()
{
 int num = 1234;
 print(num);
 return 0;
}

print传入1234进入函数，在第一个print函数中n>9，再一次进入print函数，此时n的值为123；此时n的值又>9，再一次进入print函数中如此反复，直到n<9从最后一次print函数跳出print函数至上一层的print中。

画图说明：

 

四：递归与迭代

举例：

例：求第n个斐波那契数。（不考虑溢出）
int fib(int n) {
 if (n <= 2)         
 return 1;
    else
    return fib(n - 1) + fib(n - 2);
}

但是我们发现有问题；

在使用 fib 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。

我们发现 fib 函数在调用的过程中很多计算其实在一直重复

int count = 0;//全局变量
int fib(int n) {
 if(n == 3)
 count++;
 if (n <= 2)         
 return 1;
    else
    return fib(n - 1) + fib(n - 2);
}

仅仅只是n=3就计算了非常多次，最后算出来的count结果非常的大。

在调试 factorial 函数的时候，如果你的参数比较大，那就会报错： stack overflow（栈溢出）

这样的信息。

系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一

直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。

在这种情况下我们就不建议再使用递归去解这种题目，我们此时建议使用非递归。

非递归：

//求n的阶乘
int factorial(int n)
{
        int result = 1;
        while (n > 1)
       {
             result *= n ;
             n -= 1;
       }
        return result; 
}

递归总结：

1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。

2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。

3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。