函数与递归

函数

定义（维基百科）

子程序，一般会有输入参数并有返回值，提供对过程的封装和细节的隐藏，这些代码通常被集成为软件库

库函数分类

IO函数、字符串操作函数、字符操作函数、内存操作函数、时间/日期函数、数学函数、其它函数

函数的参数

实际参数（实参）

真实传递给函数的参数。可以是常量、变量、表达式、函数等。无论实参是何类型的量，在进行函数调用时，它们必须有确定的值，以便把这些值传送给形参

形式参数（形参）

指函数名后括号内的变量。只有在函数被调用的过程中才实例化（分配内存单元），所以叫形式参数。形式参数在调用完后就自动销毁了，因此只在函数中有效

函数的定义与声明

定义

一般放在XX.c文件中，而声明一般放在XX.h文件中

// 定义add函数
int add(int x, int y){
    return x + y;
}

函数声明

一般在头文件内声明，如 int add(int x, int y);

注：要使用add函数，要引入含add函数的头文件（#include "add.h"）

头文件防止重复包含

使用 ifndef

#ifndef __头文件名_H__
#define __头文件名_H__

#endif

使用 pragma
```
#pragma once
```

函数递归

定义

程序调用自身，称为递归

核心思想

把大型复杂问题转化为相似的小问题解决，大大减少了代码量（大事化小）

函数递归的必要条件

递归需要存在限制条件，当满足条件时，递归不再继续
每次使用递归后，越来越接近这个限制条件

注：递归的使用会大量建立栈帧，对系统性能影响是巨大的

求字符串长度

计数器的写法

int my_strlen(char* arr) {
    int count = 0;
    while (*arr != '\0') {
        // 直到遇见\0停止计数
        count++;
        arr++;
    }
    return count;
}

递归的写法

int my_strlen(char* arr) {
    // 若为\0，则返回0；若不为\0，则把arr+1传过去的返回结果+1
    return (*arr == '\0') ? 0 : (my_strlen(arr + 1) + 1);
}

打印数字的每一位

循环的写法

void numprint(int num) {
    int lose = 0;
    int count; // 记录除的次数
    int record; // 记录最高位
    while (num > 9) {
        count = 0;
        record = num;
        while (record > 9) {
            record = record / 10;
            count++;
        }
        printf("%d-", record);
        lose = pow(10, count) * record;
        num = num - lose;
    }
    printf("%d\n", num);
}

递归的写法

void numprint(int num) {
    if (num > 9)
        numprint(num / 10);
    printf("%d-", num % 10);
}

求n的阶乘

int factorial(int num) {
    if (num == 1)
        return 1;
    else
        return num * function(num - 1);
}

求第n个斐波那契数列

递归的写法

long long fib(long long num) {
    if (num == 1 || num == 2)
        return 1;
    else
        return function(num - 1) + function(num - 2);
}

循环的写法

long long fib(int num) {
    long long a = 1, b = 1, ret = 0;
    int i;
    for (i = 3; i <= num; i++) {
        ret = a + b;
        a = b;
        b = ret;
    }
    return ret;
}

注：递归求解斐波那契数列性能开销是巨大的（容易栈溢出），时间复杂度也很大，推荐使用循环