文章目录前言本文旨在系统性地介绍C语言中的函数递归。一、什么是递归二、递归举例2.1、求n的阶乘2.2、顺序打印一个整数的每一位2.3、求第n个斐波那契数2.3.1、分析和代码实现2.3.2、程序性能分析2.3.3、栈溢出三、递归和循环3.1、求n的阶乘3.2、求第n个斐波那契数3.3、递归和循环的选择前言本文旨在系统性地介绍C语言中的函数递归。一、什么是递归递归是指一个函数在其定义内部调用自身的一种编程技术。它通过将复杂问题分解为规模更小的同类子问题来求解。一个正确的递归函数必须包含两个关键部分终止条件一个能直接返回结果、不再进行递归调用的特定情况如果没有终止条件递归会无限进行下去最终导致栈溢出错误。递归调用函数调用自身且问题的规模比上一次更小逐步逼近终止条件实现“大事化小”。二、递归举例2.1、求n的阶乘阶乘是指所有小于及等于该数的正整数的乘积记作 n!。注0! 1。阶乘递归的核心终止条件是 n 0 返回 1递归公式是 n * Fact(n-1)。每次调用 n 减 1逐步逼近终止条件最终逐层返回计算结果。代码示例#includestdio.h// 递归计算 n 的阶乘intFact(intn){// 1. 终止条件n 0 时0! 1if(n0)return1;// 2. 递归调用n! n * (n-1)!returnn*Fact(n-1);}intmain(){intn0;scanf(%d,n);intretFact(n);printf(%d! %d\n,n,ret);return0;}2.2、顺序打印一个整数的每一位打印整数每一位的递归思路先递归打印前 n-1 位再打印最后一位n % 10。终止条件是 n 变成一位数。这样就能按顺序输出每一位数字。代码示例#includestdio.hvoidPrint(intn){// 1. 终止条件n 是一位数直接打印if(n9){// 2. 递归调用先打印前 n-1 位Print(n/10);}// 3. 打印当前最后一位printf(%d ,n%10);}intmain(){intm0;scanf(%d,m);Print(m);return0;}2.3、求第n个斐波那契数2.3.1、分析和代码实现斐波那契数列前两个数为 0 和 1之后的每个数都是前两个数之和。代码示例#includestdio.hintFib(intn){if(n0)return0;elseif(n1)return1;elsereturnFib(n-1)Fib(n-2);}intmain(){intn0;scanf(%d,n);intretFib(n);printf(%d\n,ret);return0;}2.3.2、程序性能分析代码示例#includestdio.hintcount0;// 全局变量统计 Fib(3) 被重复计算的次数intFib(intn){if(n3)count;// 每次计算 Fib(3) 时计数if(n0)return0;elseif(n1)return1;elsereturnFib(n-1)Fib(n-2);}intmain(){intn0;scanf(%d,n);intretFib(n);printf(%d\n,ret);printf(Fib(3) 被重复计算了 %d 次\n,count);return0;}运行结果n 40102334155Fib(3)被重复计算了39088169次Fib(3) 这一个子问题就被重复计算了 3900 多万次而 Fib(2)、Fib(4) 等子问题的重复次数同样巨大。正是因为这些大量重复的计算让程序的性能很差。2.3.3、栈溢出在C语言中都需要为本次函数调用在内存的栈区申请⼀块内存空间来保存函数调用期间的各种局部变量的值这块空间被称为运行时堆栈或者函数栈帧。函数如果不返回函数对应的栈帧空间就⼀直占用所以如果函数调用中存在递归调用的话每⼀次递归函数调用都会开辟属于自己的栈帧空间直到函数递归不再继续开始回归才逐层释放栈帧空间。如果采用函数递归的方式完成代码递归层次太深就会浪费太多的栈帧空间也可能引起栈溢stack overflow的问题。三、递归和循环3.1、求n的阶乘递归写法intFact(intn){if(n0)return1;elsereturnn*Fact(n-1);}循环写法迭代intFact(intn){intret1;for(inti1;in;i){ret*i;}returnret;}3.2、求第n个斐波那契数递归写法intFib(intn){if(n0)return0;elseif(n1)return1;elsereturnFib(n-1)Fib(n-2);}循环写法迭代intFib(intn){if(n0)return0;if(n1)return1;inta0;// F(n-2)intb1;// F(n-1)intc0;// F(n)for(inti2;in;i){cab;ab;bc;}returnc;}3.3、递归和循环的选择递归用简洁性换效率循环用效率换可读性。选择原则递归深度 100 且无大量冗余计算时优先用递归否则改为循环。