C++PrimerPlus第七章函数-C++的编程模块-7.9递归-创新互联
目录
孙吴ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为成都创新互联的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:028-86922220(备注:SSL证书合作)期待与您的合作!7.9 递归
7.9.1 包含一个递归调用的递归
7.9.2 包含多个递归调用的递归
7.9 递归
下面介绍一些完全不同的内容。C++函数有一种有趣的特点——可以调用自己(然而,与C语言不同的是,C++不允许main()调用自己),这种功能被称为递归。尽管递归在特定的编程(例如人工智能)中是一种重要的工具,但这里只简单地介绍一下它是如何工作的。
7.9.1 包含一个递归调用的递归如果递归函数调用自己,则被调用的函数也将调用自己,这将无限循环下去,除非代码中包含终止调用链的内容。通常的方法将递归调用放在if语句中。例如,void类型的递归函数recurs()的代码如下:
void recurs(argumentlist)
{
statements1
if(test)
recurs(arguments)
statements2
}
test最终将为false,调用链将断开。
递归调用将导致一系列有趣的事件。只要if语句为true,每个recurs()调用都将执行statements1,然再调用recurs(),而不会执行statements2。当if语句为false时,当前调用将执行statements2。当前调用结束后,程序控制权将返回调用它的recurs(),而该recurs()将执行其statements2部分,然后结束,并将控制权返回给前一个调用,依此类推。因此,如果recurs()进行了5次递归调用,则第一个statements1部分将按函数调用的顺序执行5次,然后statements2部分将以与函数调用相反的顺序执行5次。进入5层递归后,程序将沿进入的路径返回。程序清单7.16演示了这种行为。
程序清单7.16 recur.cpp
//recur.cpp -- using recursion
#includevoid countdown(int n);
int main()
{
countdown(4); //call the recursive function
return 0;
}
void countdown(int n)
{
using namespace std;
cout<< "Counting down ... "<< n<< endl;
if (n >0)
countdown(n - 1); //function calls itself
cout<< n<< ": Kaboom!\n";
}
下面是该程序的输出:
Counting down ... 4 Counting down ... 3 Counting down ... 2 Counting down ... 1 Counting down ... 0 0: Kaboom! 1: Kaboom! 2: Kaboom! 3: Kaboom! 4: Kaboom! 注意,每个递归调用都创建自己的一套变量,因此当程序到达第5次调用时,将有5个独立的n变量,其中每个变量的值都不同。为验证这一点,读者可以修改程序清单7.16,使之显示n的地址和值: cout<< "Counting down ... "<< n<< " (n at "<< &n<< ")"<< endl; ... cout<< n<< ": Kaboom!"<< " (n at "<< &n<< ")"<< endl; 经过上述修改后,该程序的输出将与下面类似: Counting down ... 4 (n at 00EFF744) Counting down ... 3 (n at 00EFF66C) Counting down ... 2 (n at 00EFF594) Counting down ... 1 (n at 00EFF4BC) Counting down ... 0 (n at 00EFF3E4) 0: Kaboom! (n at 00EFF3E4) 1: Kaboom! (n at 00EFF4BC) 2: Kaboom! (n at 00EFF594) 3: Kaboom! (n at 00EFF66C) 4: Kaboom! (n at 00EFF744) 注意,在一个内存单元(内存地址为0012FE0C),存储的n值为4;在另一个内存单元(内存地址为0012FD34),存储的n值为3;等等。另外,注意到在Counting down阶段和Kaboom阶段的相同层级,n的地址相同。 在需要将一项工作不断分为两项较小的、类似的工作时,递归非常有用。例如,请考虑使用这种方法来绘制标尺的情况。标出两端,找到中点并将其标出。然后将同样的操作用于标尺的左半部分和右半部分。如果要进一步细分,可将同样的操作用于当前的每一部分。递归方法有时被称为分而治之策略(divide-and-conquer strategy)。程序清单7.17使用递归函数subdivide()演示了这种方法,该函数使用一个字符串,该字符串除两端为|字符外,其他全部为空格。main函数使用循环调用subdivide()函数6次,每次将递归层编号加1,并打印得到的字符串。这样,每行输出表示一层递归。该程序使用限定符std::而不是编译指令using,以提醒读者还可以采取这种方式。 程序清单7.17 ruler.cpp 下面是程序清单7.17中程序的输出: 程序说明 在程序清单7.17中,subdivide()函数使用变量level来控制递归层。函数调用自身时,将把level减1,当level为0时,该函数将不再调用自己。注意,subdivide()调用自己两次,一次针对左半部分,另一次针对右半部分。最初的中点被用作一次调用的右端点和另一次调用的左端点。请注意,调用次数将呈几何级数增长。也就是说,调用一次导致两个调用,然后导致4个调用,再导致8个调用,依此类推。这就是6层调用能够填充64个元素的原因(26=64)。这将不断导致函数调用数(以及存储的变量数)翻倍,因此如果要求的递归层数很多,这种递归方式将是一种糟糕的选择;然而,如果递归层次较少,这将是一种精致而简单的选择。 你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧//ruler.cpp -- using recursion to subdivide a ruler
#include
名称栏目:C++PrimerPlus第七章函数-C++的编程模块-7.9递归-创新互联
标题路径:http://myzitong.com/article/cchsih.html