【C语言】函数递归及例题 |
您所在的位置：网站首页 › c语言程序中函数的典型题 › 【C语言】函数递归及例题 |
【C语言】函数递归及例题
|
这一次是衔接昨天写的关于C语言函数知识点的续集，我是王木木，很高兴遇见你。 目录 7. 函数递归 7.1 什么是递归 7.2 递归的两个必要条件 7.3 递归相关例题练习 7.3.1 按顺序打印无符号整型值的每一位 7.3.2 不创建临时变量求字符串的长度 7.3.3 求n的阶乘（递归版和非递归版对比） 7.3.4 求第n个斐波那契数（递归版和非递归版对比） 7.4 递归与迭代 7. 函数递归 7.1 什么是递归定义：程序调用自身的编程技巧称为递归。 简介：递归作为一种算法再程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，通常把一个大型复杂问题层层转化为一个与原问题相似的规模较小的问题来求解，只需要少量程序就能描述出解题过程中需要的多次重复计算，大大减少了程序的代码量。 递归的主要思考方式：把大事化小。 7.2 递归的两个必要条件1） 存在限制条件，当满足这个限制条件时递归便不再继续。 2） 每次递归调用之后都会越来越接近这个限制条件。 7.3 递归相关例题练习 7.3.1 按顺序打印无符号整型值的每一位题目：接受一个无符号整型值，按照顺序打印它的每一位。 例如： 输入：1234 输出：1 2 3 4 #include void print(int i) { if (i > 9) { print(i / 10); //调用自身 } printf("%d ", i % 10); } int main() { int i; scanf("%d", &i); print(i); return 0; }
题目：编写函数，不允许创建临时变量，求字符串的长度。 #include int strlen(const char* str) { if (*str == '\0') { return 0; } else { return 1 + strlen(str + 1); } } int main() { char* p = "abcdefg"; int len = strlen(p); printf("%d\n", len); return 0; }
题目：求n的阶乘。（不考虑溢出） 解法1：递归版，数目过大时可能会栈溢出。 int factorial(int n) { if (n 1) { result *= n; n -= 1; } return result; } 7.3.4 求第n个斐波那契数（递归版和非递归版对比）题目：求第n个斐波那契数。（不考虑溢出） 解法1：数目过大时会特别耗费时间并可能造成程序崩溃的版本。 int fib(int n) { if (n 2) { n -= 1; next_result = pre_result; pre_result = result; result = next_result + pre_result; } return result; } 7.4 递归与迭代有些问题递归的效率太低，要想想如何转为迭代的方式。（比如7.3中求n的阶乘和第n个斐波那契数的问题很显然就更适合用非递归的迭代法去做。） 迭代：把一件事情反复去做。（循环就是一种迭代。） 1.很多问题是以递归的形式解释，这只是因为它比非递归的形式更为清晰。 2.但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。 3.当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时的开销。 |
【本文地址】
今日新闻 |
推荐新闻 |