递归算法的优缺点是什么(分享尾递归递归的优缺点)

网站编辑01 2022-08-01 19:34:13 阅读:24

  C允许函数调用它自己,这种调用过程称为递归(recursion)。递归有时难以捉摸,有时却很方便实用。结束递归是使用递归的难点,因为如果递归代码中没有终止递归的条件测试部分,一个调用自己的函数会无限递归。可以使用循环的地方通常都可以使用递归。有时用循环解决问题比较好,但有时用递归更好。递归方案更简洁,但效率却没有循环高。

  1 揭秘递归

  我们通过一个程序示例,来学习什么是递归。示例程序01的main()函数调用up_and_down()函数,这次调用称为“第1级递归”。然后up_and_down()调用自己,这次调用称为“第2级递归”。接着第2级递归调用第3级递归,以此类推。该程序示例共有4级递归。为了进一步深入研究递归时发生了什么,程序不仅显示了变量n的值,还显示了存储n的内存地址&n。

  首先,main()调用了带参数1的up_and_down()函数,执行结果是up_and_down()中的形式参数n的值是1,所以打印语句#1打印Level-1。

递归算法的优缺点是什么(分享尾递归递归的优缺点)

  然后,由于n小于4,up_and_down()(第1级)调用实际参数为n + e1(或2)的up_and_down()(第2级)。于是第2级调用中的n的值是2,打印语句#1打印Level 2。与此类似,下面两次调用打印的分别是Level 3和Level 4。当执行到第4级时,n的值是4,所以if测试条件为假。up_and_down()函数不再调用自己。第4级调用接着执行打印语句#2,即打印LEVEL 4,因为n的值是4。此时,第4级调用结束,控制被传回它的主调函数(即第3级调用)。在第3级调用中,执行的最后一条语句是调用if语句中的第4级调用。被调函数(第4级调用)把控制返回在这个位置,因此,第3级调用继续执行后面的代码,打印语句#2打印LEVEL 3。然后第3级调用结束,控制被传回第2级调用,接着打印LEVEL 2,以此类推。

  注意,每级递归的变量n都属于本级递归私有。这从程序输出的地址值可以看出(当然,不同的系统表示的地址格式不同,这里关键要注意,Level 1和LEVEL 1的地址相同,Level 2和LEVEL 2的地址相同,等等)。

  如果觉得不好理解,可以假设有一条函数调用链——fun1()调用fun2()、fun2()调用fun3()、fun3()调用fun4()。当fun4()结束时,控制传回fun3();当fun3()结束时,控制传回fun2();当fun2()结束时,控制传回fun1()。递归的情况与此类似,只不过fun1()、fun2()、fun3()和fun4()都是相同的函数。

  2 递归的基本原理

  初次接触递归会觉得较难理解。为了帮助读者理解递归过程,下面以程序清单9.6为例讲解几个要点。

  第1,每级函数调用都有自己的变量。也就是说,第1级的n和第2级的n不同,所以程序创建了4个单独的变量,每个变量名都是n,但是它们的值各不相同。当程序最终返回up_and_down()的第1级调用时,最初的n仍然是它的初值1(见图9.4)。

  Recursion variables.

  第2,每次函数调用都会返回一次。当函数执行完毕后,控制权将被传回上一级递归。程序必须按顺序逐级返回递归,从某级up_and_down()返回上一级的up_and_down(),不能跳级回到main()中的第1级调用。

  第3,递归函数中位于递归调用之前的语句,均按被调函数的顺序执行。例如,程序清单9.6中的打印语句#1位于递归调用之前,它按照递归的顺序:第1级、第2级、第3级和第4级,被执行了4次。

  第4,递归函数中位于递归调用之后的语句,均按被调函数相反的顺序执行。例如,打印语句#2位于递归调用之后,其执行的顺序是第4级、第3级、第2级、第1级。递归调用的这种特性在解决涉及相反顺序的编程问题时很有用。稍后将介绍一个这样的例子。

  第5,虽然每级递归都有自己的变量,但是并没有拷贝函数的代码。程序按顺序执行函数中的代码,而递归调用就相当于又从头开始执行函数的代码。除了为每次递归调用创建变量外,递归调用非常类似于一个循环语句。实际上,递归有时可用循环来代替,循环有时也能用递归来代替。

  第6,递归函数必须包含能让递归调用停止的语句。通常,递归函数都使用if或其他等价的测试条件在函数形参等于某特定值时终止递归。为此,每次递归调用的形参都要使用不同的值。例如,示例程序01的up_and_down(n)调用up_and_down(n+1)。最终,实际参数等于4时,if的测试条件(n < 4)为假。

  3 尾递归

  最简单的递归形式是把递归调用置于函数的末尾,即正好在return语句之前。这种形式的递归被称为尾递归(tailrecursion),因为递归调用在函数的末尾。尾递归是最简单的递归形式,因为它相当于循环。下面要介绍的程序示例中,分别用循环和尾递归计算阶乘。一个正整数的阶乘(factorial)是从1到该整数的所有整数的乘积。例如,3的阶乘(写作3!)是1×2×3。另外,0!等于1,负数没有阶乘。,第1个函数使用for循环计算阶乘,第2个函数使用递归计算阶乘。

二维码