【C语言】第六节 - 函数递归2
一、函数的声明和定义
1、函数声明add.h
函数的声明一般出现在函数的使用之前，要满足先声明后使用
函数声明放在头文件里
新建头文件add.h
// add.h
#pragma once
// 函数的声明
extern int Add(int x, int y);
2、函数实现add.c
函数的实现在对应的.c文件里
新建add.c文件
// add.c
int Add(int x, int y)
{
int z = x + y;
return z;
}
3、引头文件test.c
引用头文件"add.h"
就可以使用了
#include <stdio.h>
// 函数的声明一般出现在函数的使用之前，要满足先声明后使用
#include "add.h"
int main()
{
int a = 10;
int b = 20;
int ret = Add(a, b);
printf("%d\n", ret);
return 0;
}
4、引用头文件问题
引用头文件"add.h"，而不需要引用对应的"add.c"：
test.c与add.c经过各自编译后，产生对应的.obj文件，链接产生test.exe可执行程序
5、#pragma once
- 头文件出现的 #pragma once
- 它的作用主要是：防止头文件被重复多次引用
- 等价于：
#ifndef __ADD_H__
#define __ADD_H__
#endif
// #pragma once
#ifndef __ADD_H__
#define __ADD_H__
extern int Add(int x, int y);
#endif
6、分快去写的好处:
多人协作
封装和隐藏
// add.c和add.h 编译生成一个add.lib文件（点头文件右击属性- 常规- 配置类型改为静态库.lib 在debug里生成一个add.lib文件）
// add.h 和add.lib
// 在test.c里加上#pragma comment(lib, “add.lib”)导入静态库就可以使用
二、函数递归
一个过程或函数在其定义或说明过程中，有直接或间接调用自身的一种方法，多次重复计算，减少了程序的代码量
递归的主要思考方式：把大事化小
1、练习1 - 接受一个整型值（无符号），按照顺序打印它的每一位
#include <stdio.h>
void print(unsigned int n)
{
if (n > 9)
{
print(n / 10); // 123
}
printf("%d ", n % 10);
}
int main()
{
unsigned int num = 0;
scanf_s("%u", &num);
print(num);
return 0;
}
分析：
// 1. 1234>9 1234/10=123 调用print函数
// 2. 123>9 123/10=12 调用print函数
// 3. 12>9 12/10=1 调用print函数
// 4. 1<9 执行printf打印 n%10=1 打印 返回（函数从哪里调用就返回哪里）
// 5. 往下执行printf打印 此时n是12 n%12=2 打印2
// 6. 往下执行printf打印 此时n是123 n%123=3 打印3
// 7. 往下执行printf打印 此时n是1234 n%1234=4 打印4
// 8. 调用完 返回main中print 往下执行 return 0
// 1_2_3_4_
2、递归的两个必要条件
- 存在限制条件，当满足这个限制条件时，递归不再继续
- 每次递归调用之后，越来越接近这个限制条件
如果没有判断条件 -> 死递归：
每一次函数调用都要在内存中开辟空间
为main print函数各自开辟的空间 - 函数栈帧
3、练习2 - 编写函数不允许创建临时变量，求字符串的长度
变量求：
#include <stdio.h>
int main()
{
char arr[] = "abcdef";
int len = strlen(arr);
printf("%d\n", len); // 6
return 0;
}
用函数，还是有临时变量count
#include <stdio.h>
my_strlen(char* s)
{
int count = 0;
while (*s != '\0')
{
count++;
s++;
}
return count;
}
int main()
{
char arr[] = "abcdef";
// 数组名arr是数组首元素的地址 数组每个元素都是char类型 数组首元素也是char类型 数组首元素的地址是char*类型 - char*
int len = my_strlen(arr); // 数组名传过去
printf("%d\n", len);
return 0;
}
函数递归解决
#include <stdio.h>
my_strlen(char* s)
{
if (*s != '\0')
{
return 1 + my_strlen(s + 1); // 函数递归
}
else
{
return 0;
}
}
int main()
{
char arr[] = "abcdef";
int len = my_strlen(arr);
printf("%d\n", len);
return 0;
}
分析：
// 'a' != '\0' 进入if strlen递归 s+1 bcdef\0
// 'b' != '\0' 进入if strlen递归 s+1 cdef\0
// 'c' != '\0' 进入if strlen递归 s+1 def\0
// 'd' != '\0' 进入if strlen递归 s+1 ef\0
// 'e' != '\0' 进入if strlen递归 s+1 f\0
// 'f' != '\0' 进入if strlen递归 s+1 \0
// '\0' = '\0' 执行else return 0 返回
// return 1 + 0 = 1 返回1
// 1+1=2 返回2
// 1+2=3 返回3
...
// 1+5=6 返回6
// 返回main my_strlen 往下执行
// 往下执行 printf打印6
6
指针不同类型
// 字符指针+1 - 向后跳1个字节
// char *p;
// p+1 -> 向后跳1个字节
//
// 整形指针+1 - 向后跳4个字节
// int *p;
// p+1 -> 向后跳4个字节
//
// 指针加一都是指向下一个元素地址，指针类型不同，跳过的字节也不同
4、递归与迭代
4.1、练习3 - 求n的阶乘（不考虑溢出）
用循环
#include <stdio.h>
int Fac(int n)
{
int i = 0;
int ret = 0;
for (i = 1; i <= n; i++)
{
ret *= i;
}
return ret;
}
int main()
{
int n = 0;
scanf_s("%d", &n);
int ret = Fac(n);
printf("%d\n", ret);
return 0;
}
递归求
// 求n的阶乘递归公式：
// n<=1时 Fac(n) = 1
// n>1时 Fac(n) = n*fac(n-1)
#include <stdio.h>
int Fac(int n)
{
if (n <= 1)
{
return 1;
}
else
{
return n * Fac(n - 1);
}
}
int main()
{
int n = 0;
scanf_s("%d", &n);
int ret = Fac(n);
printf("%d\n", ret);
return 0;
}
分析：
// 例求3的阶乘 调用Fac函数
// 3>1 else 调用Fac(2)
// 2>1 else 调用Fac(1)
// 1<=1 if return 0 返回1
// 2*1=2 返回2
// 3*2=6 返回6
4.2、练习4 - 求第n个斐波那契数
什么是斐波那契数：
// 1 1 2 3 5 8 13 21 34 55 …
// 前2个数字之和等于第3个数字
// 求第n个斐波那契数递归公式：
// Fib(n)
// 当n<=2时 Fib(n) = 1
// 当n>2时 Fib(n) = Fib(n-1) + Fib(n-2)
用递归求
#include <stdio.h>
int count = 0;
int Fib(int n)
{
// 第三个斐波那契数被重复计算多少次
if (n == 3)
{
count++;
}
if (n <= 2)
{
return 1;
}
else
{
return Fib(n - 1) + Fib(n - 2);
}
}
int main()
{
int n = 0;
scanf_s("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
printf("count = %d\n", count);
return 0;
}
迭代（循环）
这个问题用函数递归可以使用，但是会很慢。
如果求第50个斐波那契数，需要很长时间才能算出
因为函数递归就是调用自身，多次重复计算，
计算50，就需要49和48；而49需要48和47；48需要47和46…
那么会重复多少次：
定义全局变量count，看看第三个斐波那契数被重复计算多少次
假设求第50个斐波那契数，结果count = 39088169，重复了这么多次，
所以我们要使用更加有效率的方法计算
分析：
// a = 1
// b = 1
// c = a + b
// 求完3
// 把b放进a 把c放进a
#include <stdio.h>
int Fib(int n)
{
int a = 1;
int b = 1;
int c = 0;
while (n > 2)
{
// 当n=3时 开始计算
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main()
{
int n = 0;
scanf_s("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
5、什么时候用递归
- 当解决一个问题递归和非递归都可以使用，且没有名下那问题，那就可以使用递归
- 当解决一个问题写起来很简单，非递归比较复杂，且递归没有明显问题，那就用递归
- 如果说用递归解决问题，写起来简单，但是有明显问题，那就不能使用递归，得写出非递归方式来解决
函数递归几个经典题目：
1.汉纳塔问题
2.青蛙跳台问题