递归

博客中代码已上传github，点击此处即可到达
递归指的是在函数的定义中使用函数自身的方法。

语法格式如下：

void recursion()
{
   statements;
   ... ... ...
   recursion(); /* 函数调用自身 */
   ... ... ...
}
 
int main()
{
   recursion();
}

image

C 语言支持递归，即一个函数可以调用其自身。但在使用递归时，程序员需要注意定义一个从函数退出的条件，否则会进入死循环。

递归函数在解决许多数学问题上起了至关重要的作用，比如计算一个数的阶乘、生成斐波那契数列，等等。

数的阶乘

下面的实例使用递归函数计算一个给定的数的阶乘：

double factorial(unsigned int a) {
    if (a <= 1) {
        return 1;
    }
    return a * factorial(a - 1);
}

斐波那契数列

下面的实例使用递归函数生成一个给定的数的斐波那契数列：

int fabonaci(int i) {
    if (i == 0) {
        return 0;
    } else if (i == 1) {
        return 1;
    } else {
        return fabonaci(i - 1) + fabonaci(i - 2);
    }
}

当上面的代码被编译和执行时，它会产生下列结果：

 double a = factorial(10);
    int b = fabonaci(10);
    printf(" factorial 10 is %f , fabonaci 10 is %d \n", a, b);

 factorial 10 is 3628800.000000 , fabonaci 10 is 55

递归是一个简洁的概念，同时也是一种很有用的手段。但是，使用递归是要付出代价的。与直接的语句(如while循环)相比，递归函数会耗费更多的运行时间，并且要占用大量的栈空间。递归函数每次调用自身时，都需要把它的状态存到栈中，以便在它调用完自身后，程序可以返回到它原来的状态。未经精心设计的递归函数总是会带来麻烦。

采用递归方法来解决问题，必须符合以下三个条件：

1、可以把要解决的问题转化为一个新问题，而这个新的问题的解决方法仍与原来的解决方法相同，只是所处理的对象有规律地递增或递减。

说明：解决问题的方法相同，调用函数的参数每次不同（有规律的递增或递减），如果没有规律也就不能适用递归调用。

2、可以应用这个转化过程使问题得到解决。

说明：使用其他的办法比较麻烦或很难解决，而使用递归的方法可以很好地解决问题。

3、必定要有一个明确的结束递归的条件。

说明：一定要能够在适当的地方结束递归调用。不然可能导致系统崩溃。

可变参数

有时，您可能会碰到这样的情况，您希望函数带有可变数量的参数，而不是预定义数量的参数。C 语言为这种情况提供了一个解决方案，它允许您定义一个函数，能根据具体的需求接受可变数量的参数。下面的实例演示了这种函数的定义。

int func(int, ... ) 
{
   .
   .
   .
}
 
int main()
{
   func(2, 2, 3);
   func(3, 2, 3, 4);
}

请注意，函数 func() 最后一个参数写成省略号，即三个点号（...），省略号之前的那个参数是 int，代表了要传递的可变参数的总数。为了使用这个功能，您需要使用 stdarg.h 头文件，该文件提供了实现可变参数功能的函数和宏。具体步骤如下：

• 定义一个函数，最后一个参数为省略号，省略号前面可以设置自定义参数。
• 在函数定义中创建一个 va_list 类型变量，该类型是在 stdarg.h 头文件中定义的。
• 使用 int 参数和 va_start 宏来初始化 va_list 变量为一个参数列表。宏 va_start 是在 stdarg.h 头文件中定义的。
• 使用 va_arg 宏和 va_list 变量来访问参数列表中的每个项。
• 使用宏 va_end 来清理赋予 va_list 变量的内存。

现在让我们按照上面的步骤，来编写一个带有可变数量参数的函数，并返回它们的平均值：

double average_nums(int num,...){
    va_list list;
    double sum=0;

    /* 为 num 个参数初始化 valist */
    va_start(list,num);


    /* 访问所有赋给 valist 的参数 */
    /* 访问所有赋给 valist 的参数 */
    for (int i = 0; i < num; i++)
    {
        sum += va_arg(list, int);
    }
    /* 清理为 valist 保留的内存 */
    va_end(list);

    return sum/num;
}

double c = average_nums(5, 1, 600, 5, 7, 9);
    printf(" average_nums 5 is %f ",c);

 average_nums 5 is 124.400000

C 函数要在程序中用到以下这些宏:

void va_start( va_list arg_ptr, prev_param ); 
type va_arg( va_list arg_ptr, type ); 
void va_end( va_list arg_ptr );

va_list: 用来保存宏va_start、va_arg和va_end所需信息的一种类型。为了访问变长参数列表中的参数，必须声明 va_list 类型的一个对象，定义： typedef char * va_list;

va_start: 访问变长参数列表中的参数之前使用的宏，它初始化用 va_list 声明的对象，初始化结果供宏 va_arg 和 va_end 使用；

va_arg: 展开成一个表达式的宏，该表达式具有变长参数列表中下一个参数的值和类型。每次调用 va_arg 都会修改用 va_list 声明的对象，从而使该对象指向参数列表中的下一个参数；

va_end: 该宏使程序能够从变长参数列表用宏 va_start 引用的函数中正常返回。

va 在这里是 variable-argument(可变参数) 的意思。

这些宏定义在 stdarg.h 中，所以用到可变参数的程序应该包含这个头文件。

下面我们写一个简单的可变参数的函数，该函数至少有一个整数参数，第二个参数也是整数，是可选的。函数只是打印这两个参数的值。

int changeable_varity(char *msg, ...) {

    va_list argp;                    /* 定义保存函数参数的结构 */
    int argno = 0;                    /* 纪录参数个数 */
    char *para;                        /* 存放取出的字符串参数 */
    va_start( argp, msg );          /* argp指向传入的第一个可选参数，      msg是最后一个确定的参数 */

    while (1)
    {
        para = va_arg( argp, char *);                 /*      取出当前的参数，类型为char *. */
        if ( strcmp( para, "/0") == 0 )
            /* 采用空串指示参数输入结束 */
            break;
        printf("Parameter #%d is: %s\n", argno, para);
        argno++;
    }
    va_end( argp );                                   /* 将argp置为NULL */
    return 0;
}

changeable_varity("FAKER","what", "are", "you", "nong", "sha", "lei","/0");

Parameter #0 is: what
Parameter #1 is: are
Parameter #2 is: you
Parameter #3 is: nong
Parameter #4 is: sha
Parameter #5 is: lei

从这个函数的实现可以看到,我们使用可变参数应该有以下步骤:

• 1)首先在函数里定义一个 va_list 型的变量,这里是 arg_ptr，这个变量是指向参数的指针。
• 2)然后用 va_start 宏初始化变量 arg_ptr，这个宏的第二个参数是第一个可变参数的前一个参数，是一个固定的参数。
• 3)然后用 va_arg 返回可变的参数，并赋值给整数 j。va_arg 的第二个参数是你要返回的参数的类型，这里是int型。
• 4)最后用 va_end 宏结束可变参数的获取。然后你就可以在函数里使用第二个参数了。如果函数有多个可变参数的，依次调用 va_arg 获取各个参数。

内存管理

本章将讲解 C 中的动态内存管理。C 语言为内存的分配和管理提供了几个函数。这些函数可以在 <stdlib.h> 头文件中找到。

序号	函数和描述
1	void *calloc(int num, int size); 在内存中动态地分配 num 个长度为 size 的连续空间，并将每一个字节都初始化为 0。所以它的结果是分配了 num*size 个字节长度的内存空间，并且每个字节的值都是0。
2	void free(void *address); 该函数释放 address 所指向的内存块,释放的是动态分配的内存空间。
3	void *malloc(int num); 在堆区分配一块指定大小的内存空间，用来存放数据。这块内存空间在函数执行完成后不会被初始化，它们的值是未知的。
4	*void *realloc(void address, int newsize); 该函数重新分配内存，把内存扩展到 newsize。

注意：void * 类型表示未确定类型的指针。C、C++ 规定 void * 类型可以通过类型转换强制转换为任何其它类型的指针。

动态分配内存

编程时，如果您预先知道数组的大小，那么定义数组时就比较容易。例如，一个存储人名的数组，它最多容纳 100 个字符，所以您可以定义数组，如下所示：

char name[100];

但是，如果您预先不知道需要存储的文本长度，例如您向存储有关一个主题的详细描述。在这里，我们需要定义一个指针，该指针指向未定义所需内存大小的字符，后续再根据需求来分配内存，如下所示：

void dynamic_allocation_memory() {
    char name[100];
    char *description;

    strcpy(name, "Tony Anndy");
    // description = (char *) _malloc(200 * sizeof(char));
    /* 动态分配内存 */
    description = (char *) malloc(200 * sizeof(char));

    if (description == NULL) {
        fprintf(stderr, "Error - unable to allocate required memory\n");
    } else {
        strcpy(description, "Tony Anndy is DPS gay in class 10th");
    }
    printf("Name = %s\n", name);
    printf("Description: %s\n", description);
};

当上面的代码被编译和执行时，它会产生下列结果：

Name = Tony Anndy
Description: Tony Anndy is DPS gay in class 10th

上面的程序也可以使用 calloc() 来编写，只需要把 malloc 替换为 calloc 即可，如下所示：

calloc(200, sizeof(char));

当动态分配内存时，您有完全控制权，可以传递任何大小的值。而那些预先定义了大小的数组，一旦定义则无法改变大小。

重新调整内存的大小和释放内存

当程序退出时，操作系统会自动释放所有分配给程序的内存，但是，建议您在不需要内存时，都应该调用函数 free() 来释放内存。

或者，您可以通过调用函数 realloc() 来增加或减少已分配的内存块的大小。让我们使用 realloc() 和 free() 函数，再次查看上面的实例：

void dynamic_allocation_memory() {
    char name[100];
    char *description;

    strcpy(name, "Tony Anndy");
    // description = (char *) _malloc(200 * sizeof(char));
    /* 动态分配内存 */
    description = (char *) malloc(80 * sizeof(char));

    if (description == NULL) {
        fprintf(stderr, "Error - unable to allocate required memory\n");
    } else {
        strcpy(description, "Tony Anndy is DPS gay in class 10th ");
    }

    /* 假设您想要存储更大的描述信息 */
    description = realloc(description, 100 * sizeof(char));
    if (description == NULL) {
        fprintf(stderr, "Error - unable to allocate required memory\n");
    } else {
        strcat(description, "She is in class 10th");
    }

    printf("Name = %s\n", name);
    printf("Description: %s\n", description);
};

对于 void 指针，GNU 认为 void * 和 char * 一样，所以以下写法是正确的:

description = malloc( 200 * sizeof(char) );

但按照 ANSI(American National Standards Institute) 标准，需要对 void 指针进行强制转换，如下:

description = (char *)malloc( 200 * sizeof(char) );

同时，按照 ANSI(American National Standards Institute) 标准，不能对 void 指针进行算法操作:

void * pvoid;
pvoid++; //ANSI：错误
pvoid += 1; //ANSI：错误
// ANSI标准之所以这样认定，是因为它坚持：进行算法操作的指针必须是确定知道其指向数据类型大小的。

int *pint;
pint++; //ANSI：正确

代码已上传github，点击此处即可到达