函数练习-2

函数递归

什么是递归？

程序调用自身的编程技巧称为递归(recursion)。递归做为一种算法在程序设计语言中广泛应用。

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的主要思考方式在于: 把大事化小

例如：

#include <stdio.h>
int main()
{
    printf("test\n");
    main();
    return 0;
}

比如，main函数也是一个函数，main函数自己调用自己，这就是一个递归，程序会一直打印“test”，但是会不会无限制打印类似死循环呢？答案是不会，为什么呢？就要看一下递归的两个必要条件。

递归的两个必要条件

存在限制条件，当满足这个限制条件的时候，递归便不再继续。
每次递归调用之后越来越接近这个限制条件。

所以说，如果不满足递归的两个必要条件，可能会造成程序栈溢出（stack overflow），直接死递归结束程序。

调试之后发现程序发现异常，stack overflow，栈溢出。

练习1: 接受一个整型值(无符号)，按照顺序打印它的每一位。例如:输入:1234，输出1 2 3 4.

假设输入1234，我们要将这个数按顺序输出1 2 3 4，是不是应该先思考怎么将这个数提取出来，那么我们怎么提取这个数字呢？

那么我们有：

1234 % 10 = 4

1234 / 10 = 123

123 % 10 = 3

……

通过“模运算”和“除运算”，我们可以从后往前求出4、3、2、1。那么我们第一个想到的思路是不是定义一个数组，然后通过循环将求出的值放进数组里，再输出。这是一种实现思路。

但是数组的大小定义多少呢？万一我定义了一个5个数的数组，输入的数字却有6位数，多出来的一位数放哪里呢？同时这样的方法也比较麻烦。

这个时候，我们可以试着用递归来解决这个问题，先确定递归的两个必要条件：

存在限制条件，当满足这个限制条件的时候，递归便不再继续。
每次递归调用之后越来越接近这个限制条件。

那么我们就有以下代码：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

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

int main()
{
    unsigned int num = 0;
    scanf("%u", &num);
    print(num);
    return 0;
}

那么这个代码怎么理解呢？

首先从“main”函数开始执行程序，从“scanf”语句接受输入的数字：1234

与此同时下一行调用print，此时传递的参数是num=1234

在此时，进入到print函数内部，首先进行判断，num的值是不是大于9，如果是，就执行语句print(num/10)。

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

那么这个时候就递归调用了他本身print函数，这个时候传递的参数num是多少呢，num=num/10=123，也就是说，下一层函数的参数值是123。

123是否大于9？显而易见的，那么又进行一层递归，此时传递参数为12。

12是否大于9？由此又进行一层递归，此时参数传递的就是1了，很显然，1不满足num>9的条件，跳到下一条语句：

1	printf("%d ", num % 10);

递归最里层传递的参数num的值是1，那么他打印出来的就是“1 ”，此时最里层递归的函数调用完毕，返回上一层函数调用的代码（此时num的值是12），那么12%10之后余2，就是打印的结果。

再上一层 123 % 10 = 3，再再上一层 1234 % 10 = 4。

以上就是函数的运行大致流程，一个递归的简单应用。现在分析一下以上程序是否满足递归的两个必要条件呢？

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

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

答案是肯定的，限制条件就是num是否大于9。

1	if (num > 9)

因为num是一个无符号整型变量，大于9就说明他还有两位数以上，还需要继续递归调用函数进行处理。

那么每次递归调用之后是否越来越接近这个限制条件呢？

1	print(num / 10);

答案也是肯定的，每次调用的传递的参数值，都进行一个“ / 10 ”操作，这样一个较大的数就会越来越接近10以下，也就是接近num<9，从而结束。

练习2:编写函数不允许创建临时变量，求字符串的长度。

通常怎么求字符串长度呢？在C语言中有一个库函数“strlen”用于求字符串长度，size_t strlen( const char *****string );

#include <stdio.h>
#include <string.h>
int main()
{
    char arr[] = "Hello";
    printf("%zd", strlen(arr));
    return 0;
}

题目的要求是自己编写一个函数求字符串的长度，在传统编程的思想来看也是非常简单的，就是通过循环判断它等不等于’\0’，如果等于，就是字符串结尾了，打印此时计数的值就是字符串长度。

但是题目还有一个要求：不允许创建临时变量，这样就难办了，但是我们今天学习的是递归，那么有没有可能按照递归的思想拆分（大事化小）这个问题呢？

假设字符串为”Hello“，那么我们在内存中存放这个变量应为 ‘H’ ‘e’ ‘l’ ‘l’ ‘o’ ‘\0’，怎么拆分呢？

假设我们定义一个”strl“函数，那么将字符串传递进去初始参数字符串”Hello“，能不能把他拆分成？

strl("Hello");
1 + strl("ello");
1+1+strl("llo");
……
1+1+1+1+1+0=5

通过递归的思想，我们可以写出以下代码：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

int strl(char* str)
{
    if (*str != '\0')
        return 1 + strl(str + 1);
    else
        return 0;
}

int main()
{
    char str[] = "Hello";
    printf("%d", strl(str));
    return 0;
}