C语言递归函数
递归(recursive)函数是“自己调用自己”的函数,无论是采用直接或间接调用方式。间接递归意味着函数调用另一个函数(然后可能又调用第三个函数等),最后又调用第一个函数。因为函数不可以一直不停地调用自己,所以递归函数一定具备结束条件。
在例 1 中,递归函数 binarySearch()实现二元搜索算法,在排序好的数组中找到特定元素。首先,该函数根据搜索条件比较数组最中间的元素。如果相同,就返问该元素的指针,表示找到了;如果不相同,该函数会调用自己,在可能存在满足搜索条件的一半数组中搜索,一直递归地进行下去,指导找到满足搜索条件的元素。如果剩下数组的长度为 0,则表示找不到,那么递归就会结束。
【例1】函数 binarySearch()
对于有 n 个元素的数组来说,二元搜索算法进行最多 1+log2(n)次比较。如果有一百万个元素,最多比较 20 次,也就是最多 20 次递归执行函数 binarysearch()。
递归函数基于了这样一个事实:每次调用函数时,都会重新建立动态变量。这些变量,以及返回时需要的调用者地址,都存储在栈中,每次函数递归都会造成栈上新增一块数据。程序员要确保栈的空间够大,足以容纳递归的中间处理过程。不过例 1 中的函数 binarySearch()对于栈空间的要求并不大。
递归函数是采用逻辑方式来实现自然递归规律的算法,例如二元搜索技术,或者树状结构导航(navigation)。
然而,即使递归函数可以对某些问题提供优雅而紧凑的解决方案,但采用简单循环的解决方案也常常是可行的。例如,可以用循环改写例 1 的二元搜索算法,而不使用递归函数调用。在这种情况下,采用循环的解决方案通常会比采用递归的解决方案执行效率更高。
在例 1 中,递归函数 binarySearch()实现二元搜索算法,在排序好的数组中找到特定元素。首先,该函数根据搜索条件比较数组最中间的元素。如果相同,就返问该元素的指针,表示找到了;如果不相同,该函数会调用自己,在可能存在满足搜索条件的一半数组中搜索,一直递归地进行下去,指导找到满足搜索条件的元素。如果剩下数组的长度为 0,则表示找不到,那么递归就会结束。
【例1】函数 binarySearch()
// 函数 binarySearch() 在排序好的数组中搜索 // 参数:需要搜索的元素值;待搜索的long类型数组;数组的长度 // 返回值:指向满足搜索条件的元素的指针,或者为NULL,如果数组中没有元素满足搜索条件。 long *binarySearch( long val, long array[ ], int n ) { int m = n/2; if ( n <= 0 ) return NULL; if ( val == array[m] ) return array + m; if ( val < array[m] ) return binarySearch( val, array, m ); else return binarySearch( val, array+m+1, n-m-1 ); }
对于有 n 个元素的数组来说,二元搜索算法进行最多 1+log2(n)次比较。如果有一百万个元素,最多比较 20 次,也就是最多 20 次递归执行函数 binarysearch()。
递归函数基于了这样一个事实:每次调用函数时,都会重新建立动态变量。这些变量,以及返回时需要的调用者地址,都存储在栈中,每次函数递归都会造成栈上新增一块数据。程序员要确保栈的空间够大,足以容纳递归的中间处理过程。不过例 1 中的函数 binarySearch()对于栈空间的要求并不大。
递归函数是采用逻辑方式来实现自然递归规律的算法,例如二元搜索技术,或者树状结构导航(navigation)。
然而,即使递归函数可以对某些问题提供优雅而紧凑的解决方案,但采用简单循环的解决方案也常常是可行的。例如,可以用循环改写例 1 的二元搜索算法,而不使用递归函数调用。在这种情况下,采用循环的解决方案通常会比采用递归的解决方案执行效率更高。
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频