预备知识

递归算法的含义: 若一个算法直接或间接调用自己本身,则称这个算法是递归算法,递归算法的执行过程是不断地自调用,直到到达递归出口才结束自调用过程,到达递归出口后,递归算法开始按最后调用的过程最先返回的次序返回,返回到最外层的调用语句时递归算法执行过程结束[6].

定理 1 对于任意整数前 ,前N个整数的和 值为  [12].

1.递归算法的介绍

递归很容易描述,但却很难理解.简单地说,递归是函数调用自身的过程.在C语言中这实际上想当容易执行.我们已经知道如何编写在其中一个函数上调用另一个函数的程序,如曾经最著名的C语言程序所示:

# include <stdio.h>

int main(void)

  {

    printf(“hello,world!\n”);

    return 0;

}

在有些语言中,如果程序结束调用自身(包括间接调用),编译者不得不做许多额外的工作来调用一个函数.但是在C语言中则不必如此.例如下面这个不足道的示例:

unsigned int

recurse_n_times(unsigned int n){

   if(n = = 0)

      return 0;

   else return recurse_n_times(n-1) + 1;

}

该函数返回其变元.但这个路径是很曲折.当给它传递一个大于0的数时,函数就调用自身那么多次,只为了结果返回一开始传递给它的值.

这不是一个特别实际的示例——没有人会在程序中编写这种代码——但是它显示了在C语言中实现递归有多么容易.相当简单,编程者不用”实现”递归,它就是一个语言特征.

从C语言之外的更广泛意义来看,递归就是通过回答同一问题的一个更简单版本而回答问题的过程.假设我们需要执行一件困难的任务,如果我们把它很容易地分解成一系列更简单的任务,并且每个简单的任务都可以分解成更简单的任务,这时实际上我们并没有做任何困难的事就解决了困难的问题.

事实的确如此,遗憾的是,这个简单概念的要点不容易掌握.下面我们来具体认识一下递归算法.