C 语言学习历程：（第七章）函数递归・在自我调用中探寻问题的精妙解法

第七章：函数递归

函数递归就是函数自己调用自己。其思想是将一个大型复杂问题层层转化为一个与原问题相似，但规模较小的子问题来求解；直到子问题不能再被拆分，递归就结束。递归中的递就是递推的意思，归就是回归的意思。

限制条件：

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

1. 求 n 的阶乘

一个正整数的阶乘是所有小于及等于该数的正整数的积，并且0的阶乘为1

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>//阶乘//定义阶乘函数intfactorial(intn){if(n==0){return1;}returnfactorial(n-1)*n;}intmain(){//方法一：循环//int num = 1;//for (int i = 1; i <= 10; i++)//{// num *= i;//}//方法二 ：递归，逻辑如下// 0!= 1// 1!= 1 = 0! * 1// 2!= 1 * 2 = 1! * 2// 3!= 1 * 2 * 3 = 2! * 3// 4!= 1 * 2 * 3 * 4 = 3! * 4// n! = (n-1)! * nintn=0;scanf("%d",&n);printf("%d",factorial(n));return0;}

2. 顺序打印一个整数的每一位

输入一个整数。按照顺序打印整数的每一位，例如输入：1234 输出： 1 2 3 4

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>//顺序打印一个整数的每一位// 1 : 1// 12 : 1 2 = print_num(1) 2// 123 : 1 2 3 = print_num(12) 3// 1234 : 1 2 3 4 = print_num(123) 4// n : print_num(n / 10) n % 10voidprint_num(intnum){//方法一if(num/10==0){printf("%d",num);//个位数返回本身}else{print_num(num/10);//递归调用，去掉个位数printf(" %d",num%10);}//方法二//if (num > 9) //不是个位则进行递归//{// print_num(num / 10);//递归调用，去掉个位数//}//printf("%d ", num % 10);//if语句执行完还会打印数字，而不是else的关系}intmain(){intnum=0;scanf("%d",&num);print_num(num);//定义打印每一位数字的函数return0;}

3. 求 n 的 k 次方

输入一个整数 n 递归实现 n 的 k 次方

//递归实现n的k次方// 2^1 = 2// 2^2 = 2^1 *2// 2^3 = 2^2 *2// n^k = n^(k-1) * n//求n的k次方函数intexponent(intn,intk){if(k==1){returnn;//如果是1次方，返回本身}returnexponent(n,k-1)*n;}intmain(){intn=0;intk=0;scanf("%d%d",&n,&k);printf("%d",exponent(n,k));return0;}

4. 递归与迭代

在C语言中每一次函数调用，都需要为本次函数调用在内存的栈区，申请一块内存空间来保存函数调用期间的各种局部变量的值，这块空间被称为运行时堆栈，或者函数栈帧。

函数不返回，函数对应的栈帧空间就⼀直占⽤，所以如果函数调⽤中存在递归调⽤的话，每⼀次递归函数调⽤都会开辟属于⾃⼰的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。 所以如果采⽤函数递归的⽅式完成代码，递归层次太深，就会浪费太多的栈帧空间，也可能引起栈溢出的问题。

当不使用递归，通常就是迭代的方式（通常是循环）

4.1 求第 n 个斐波那契数

计算第n个斐波那契数，这个程序便不适合用递归求解

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>//递归和迭代//求第n个斐波那契数//1 1 2 3 5 8 13 21 ...：前两个数相加等于后面的数字//第n个斐波那契数字：f(n) = f(n-2) + f(n-1)//递归实现斐波那契会有大量重复计算，效率低下intf_add(intnum){if(num==1||num==2){return1;}else{returnf_add(num-2)+f_add(num-1);}}intmain(){intnum=0;//定义变量接受第几个斐波那契数字scanf("%d",&num);f_add(num);//调用函数printf("%d\n",f_add(num));//打印结果return0;}

迭代实现：

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>//迭代实现intmain(){intleft_1=1;//最左边第一个数intleft_2=1;//最左边第二个数intnum=0;//定义变量接受第几个斐波那契数字intn=1;//定义变量计算数字，初始值为1scanf("%d",&num);for(inti=0;i<num-2;i++){n=left_1+left_2;//计算当前数left_1=left_2;//更新左边第一个数left_2=n;//更新左边第二个数}printf("%d\n",n);//打印结果return0;}

第八章：操作符详解

总结

本文是在鹏哥 C 语言集训营学习过程中所记录的学习笔记，梳理了核心知识点，同时也记录了本人实操验证的代码案例，供后续学习复盘使用。