什么是递归函数
前面的学习过程中,我们已经看到过很多调用其他函数的函数实例。例如,函数 A 可以调用函数 B,而函数 B 又可以调用函数 C。
实际上,函数也可以调用它自己。调用自己的函数称为递归函数。来看以下 message 函数:
要使递归函数有用,则递归函数必须有一个方法来控制递归调用的次数。以下是对 message 函数的修改。它传递了一个整数参数,该参数将保存函数调用自己的次数。
图 1 递归函数调用过程
图 1 直观地说明了两次独立的 message 函数调用。每次调用该函数时,会在内存中创建一个 times 参数的新实例。函数第一次被调用时,times 参数被设置为 3;当函数调用自己时,会创建一个新的 times 实例,并将值 2 传递给它。如此循环往复,直到传递给函数的值变成了 0,如图 2 所示。
图 2 通过 times 参数控制递归函数的调用次数
从图 2 可以看到,该函数将被调用 4 次,所以递归的深度是 4。当函数到达第 4 次调用时,times 参数将被设置为 0。此时,if 语句将停止调用的递归链,并且将返回函数的第 4 个实例。程序的控制权将从函数的第 4 个实例返回到第 3 个实例中调用递归函数语句所在的位置:
下面的程序演示了修改后的递归 message 函数,它可以显示每次调用时参数的值。
为了进一步说明这个递归函数的内部工作,不妨来看一看另一个版本的程序。下面的程序中,每次进入函数都会显示一条消息,并且在函数返回之前显示另一条消息。
例如,如果有一长串的名称列表需要排序,则可以将列表分成两个子列表,并将两个子列表分配给两个不词的人来排序。一旦子列表完成排序,它们可以通过合适的整理过程合并形成原始列表的排序版本中。
在这种情况下,排序子列表的问题就是相同类型的更简单的问题。子列表实际上还可以再拆分,而基本情况就出现在子列表中只有一个名称时。
现在来看一个执行实用任务的简单递归示例。函数 frequency 可以计算特定字符出现在字符串中的次数。
第一个 if 语句确定是否已出现基本情况,即到达字符串的结尾:
例如,当函数 A 调用函数 B,而函数 B 又反过来调用函数 A 时,就会发生这种情况。在间接递归中甚至可能包含若干个函数。例如,函数 A 调用函数 B,函数 B 调用函数 C,而函数 C 又调用函数 A。
实际上,函数也可以调用它自己。调用自己的函数称为递归函数。来看以下 message 函数:
void message() { cout << "This is a recursive function. \n"; message(); }该函数显示字符串 "This is a recursive function.",然后调用它自己。每次它调用自己时,循环都会重复。现在应该能发现该函数的问题,因为它没有办法停止递归调用。这个函数就像一个无限循环,因为没有代码阻止它重复。
要使递归函数有用,则递归函数必须有一个方法来控制递归调用的次数。以下是对 message 函数的修改。它传递了一个整数参数,该参数将保存函数调用自己的次数。
void message(int times) { if (times > 0) { cout << "This is a recursive function.\n"; message(times - 1); } }该函数包含一个控制递归的 if 语句。只要 times 参数大于零,它将显示消息并再次调用自己。每次它调用自己时,都会传递 times-1 作为参数。例如,假设有一个程序使用以下语句来调用该函数:
message(3);
参数 3 将导致函数被调用 4 次。第一次调用函数时,if 语句将显示消息并以 2 作为参数调用自身,如图 1 所示。图 1 递归函数调用过程
图 1 直观地说明了两次独立的 message 函数调用。每次调用该函数时,会在内存中创建一个 times 参数的新实例。函数第一次被调用时,times 参数被设置为 3;当函数调用自己时,会创建一个新的 times 实例,并将值 2 传递给它。如此循环往复,直到传递给函数的值变成了 0,如图 2 所示。
图 2 通过 times 参数控制递归函数的调用次数
从图 2 可以看到,该函数将被调用 4 次,所以递归的深度是 4。当函数到达第 4 次调用时,times 参数将被设置为 0。此时,if 语句将停止调用的递归链,并且将返回函数的第 4 个实例。程序的控制权将从函数的第 4 个实例返回到第 3 个实例中调用递归函数语句所在的位置:
if (times > 0) { cout << "This is a recursive function.\n"; message(times - 1); }因为在函数调用之后没有更多的语句要执行,所以函数的第 3 个实例会将程序的控制权返回给第 2 个实例。如此重复,直到函数的所有实例都返回。
下面的程序演示了修改后的递归 message 函数,它可以显示每次调用时参数的值。
// This program demonstrates a simple recursive function. #include <iostream> using namespace std; //Function prototype void message(int); int main() { message(3); return 0; } void message(int times) { if (times > 0) { cout << "Message " << times << "\n"; message(times - 1); } }程序输出结果:
Message 3
Message 2
Message 1
为了进一步说明这个递归函数的内部工作,不妨来看一看另一个版本的程序。下面的程序中,每次进入函数都会显示一条消息,并且在函数返回之前显示另一条消息。
// This program demonstrates a simple recursive function. #include <iostream> using namespace std; // Function prototype void message(int); int main() { message(3); return 0; } void message(int times) { cout << "Message " << times << ".\n"; if (times > 0) { message(times - 1); } cout << "Message " << times << " is returning.\n"; }程序输出结果:
Message 3.
Message 2.
Message 1.
Message 0.
Message 0 is returning.
Message 1 is returning.
Message 2 is returning.
Message 3 is returning.
例如,如果有一长串的名称列表需要排序,则可以将列表分成两个子列表,并将两个子列表分配给两个不词的人来排序。一旦子列表完成排序,它们可以通过合适的整理过程合并形成原始列表的排序版本中。
在这种情况下,排序子列表的问题就是相同类型的更简单的问题。子列表实际上还可以再拆分,而基本情况就出现在子列表中只有一个名称时。
现在来看一个执行实用任务的简单递归示例。函数 frequency 可以计算特定字符出现在字符串中的次数。
int frequency(char ch, string inputString, int position) { if (position == inputString. length () ) //基本情况 return 0; if (inputString[position] == ch) return 1 + frequency(ch, inputString, position+1); else return frequency(ch, inputString, position+1); }该函数的参数包括:
- ch:要搜索和计数的字符。
- inputString:要搜索的字符串。
- position:搜索的起始下标。
第一个 if 语句确定是否已出现基本情况,即到达字符串的结尾:
if (position == inputString.length())
return 0;
if (inputString[position] == ch) return 1 + frequency(ch, inputString, position+1); else return frequency(ch, inputString, position+1);如果 inputString [position] 是搜索字符,则函数执行递归调用。返回语句返回 1 加上搜索字符在字符串中出现的次数,从 position+1 开始。如果 inputString [position] 不是搜索字符,则会进行递归调用以搜索字符串的其余部分。下面的程序演示了以上示例。
// This program demonstrates a recursive function for // counting the number of times a character appears // in a string. #include <iostream> #include <string> using namespace std; // Function prototype int frequency(char ch, string inputString , int pos); int main() { string inputString = "abcddddef"; cout << "The letter d appears " << frequency ('d', inputString, 0) << " times.\n"; return 0; } int frequency(char ch, string inputString, int position) { if (position == inputString.length()) //base case return 0; if (inputString[position] == ch) return 1 + frequency(ch, inputString, position+1); else return frequency(ch, inputString, position+1); }程序输出结果:
The letter d appears 4 times.
直接递归和间接递归
迄今为止,我们所讨论的例子都是直接调用自己的递归函数,这称为直接递归。也可以在程序中创建间接递归。例如,当函数 A 调用函数 B,而函数 B 又反过来调用函数 A 时,就会发生这种情况。在间接递归中甚至可能包含若干个函数。例如,函数 A 调用函数 B,函数 B 调用函数 C,而函数 C 又调用函数 A。
所有教程
- 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视频