学C笔记归纳 第十三篇——函数3 递归（重点）

1.什么叫递归？

        递归是一种编程技巧，程序调用自身的编程技巧称为 “递归”，应用广泛。

2.描述递归

        递归把一个大型复杂问题层层转化为一个与原问题相似的规模较小的问题来求解，

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

3.递归的核心思想

        把大事化小。 

来看一个例子：输入一个无符号整型值，按照顺序打印它的每一位 

#include <stdio.h>

void print(unsigned int x)
{
    int num = x % 10;
    if (num)
    {
        print(x/ 10); //递
        printf("%d ", num); //归
    }
    
}
int main()
{
    unsigned int n = 0;
    scanf("%u", &n);
    print(n); //接受一个无符号整型值，按照顺序打印它的每一位
    return 0;
}

4.该例子的抽象理解

        递归递归，先递递递...再归归归...;

        递：1p中断将处理过的参数传给下一个 2p处理传3p......直到触发限制条件开始归；

        归：归：递完，执行递语句之后的语句，从后向前......完了在执行3p的归、2p、1p

        递有多少，归就有多少。

5.Stack overflow(栈溢出）

        递如果没有终止条件，就会不停的调用自身，每一次函数调用都会在栈区申请空间，最终导致栈溢出。

6.递归的两个必要条件：

        ·存在限制条件，当满足这个限制条件的时候，递归便不在继续；

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

练习：模拟strlen功能写个函数，不能创建临时变量。

#include <stdio.h>

//模拟strlen功能写个函数，不能创建临时变量。
//int my_strlen(char str[]) //参数写成数组形式也行
int my_strlen(char* str) //参数写成指针形式
{
    if(*str != '\0') //限制条件, 注意是单引号，双引号判定会出错，陷入递归导致栈溢出
        return 1 + my_strlen(str+1); //最好不要写str++，它会改变str本身
    else
        return 0;
}
int main()
{
    char arr[] = "abc"; //{"1","2","3","\0"}
    int len = my_strlen(arr);
    printf("%d\n", len);
    return 0;
}

并不是所有问题都适合递归求解，例如 打印第n 个斐波那契数列 数：

//  打印第n 个斐波那契数列 数：1 1 2 3 5 8 13 

int count = 0;
int fib(int x)
{
　　if (x == 3)
　　count++;
　　if (x > 2)
　　　　return fib(x - 1) + fib(x - 2);
　　else
　　{
　　　　return 1;
　　}
}
int main()
{
　　int n = fib(5);
　　printf("%d\n",n);
　　printf("count =%d\n", count);
　　return 0;
}

但如果打印第30个，记录x=3计算次数呢

#include <stdio.h>

// 打印第n 个斐波那契数列 数：1 1 2 3 5 8 13
int count = 0;
int fib(int x)
{
　　if (x == 3)
　　　　count++;
　　if (x > 2)
　　　　return fib(x - 1) + fib(x - 2);
　　else
　　{
　　　　return 1;
　　}
}
int main()
{
　　int n = fib(30);
　　printf("%d\n",n);
　　printf("count =%d\n", count);
　　return 0;
}

317811次！这个计算量就恐怖了，函数递归会不断占用栈区空间，如果是第60、100呢？显然有几率发生栈溢出现象。故此时递归求解不可取。

int main()
{
    int n = 30;
    int a = 1;
    int b = 1;
    int c = 1;
    while (n>=3)
    {
        c = a + b;
        a = b;
        b = c;
        n--;
    }
    printf("%d\n", c);
    //printf("count =%d\n",count);
    return 0;
}

因此，在解决问题时，我们的权衡利弊十分重要，如果写个函数，用递归轻松解决问题且不会占用太多内存空间，就用递归方式，反之非递归。