递归与分治策略(一)

任何可以用计算机求解的问题所需的计算时间都与其规模大小有关。问题的规模越小,解题所需的计算机时间往往也越短,从而也比较容易处理。例如,对于n个元素的排序问题,当n=1时,不需要任何计算。n=2时,只要做一次比较即刻排好序。n=3时只要两次比较即可。但是当n变得特别大的时候,问题就不这么容易解决了。想要直接处理一个较大的问题,有时是相当困难的。

分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同的问题,以便各个击破,分而治之。

如果原问题可分割成k个子问题,1<k≤n,且这些子问题都可解,并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是

原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而使其规模却不断缩小,最终使子问题缩小到很容易求出其解。由此自然引出递归算法。分治和递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效的算法。

递归的概念

直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。

或许这两句话不太好理解,我们来看看几个实例。

阶乘函数

阶乘函数可递归地定义为

$$n!=\left\{\begin{matrix}
1 &  &n=0 \\
n(n-1)!& & n>0
\end{matrix}\right.$$

阶乘函数的自变量n的定义域是非负整数。递归式的第一式给出了这个函数的初始值(是非递归定义的,也就是直接确定的值0).每个递归函数都必须有非递归定义的初始值,否则递归函数就无法计算。比如这个阶乘函数,如果你没有非递归定义的初始值,也就是你只有第二个式子,当n=1时,1!=1*(1-1)!,而当n=0时,是无法用公式表示的,函数就出问题了。递归式的第二式用较小自变量的函数值来表示较大自变量的函数值的方式来定义n的阶乘。比如5的阶乘就等于5乘以4的阶乘,用公式表达5!=5*(4!),也就是5!=5*(5-1)!,那么可以很容易的得到n!=n*(n-1)!。这是数学上的实现方法,如何用函数来实现呢?其实很简单,只需要短短几行代码。

int factorial(int n )   //定义阶乘函数
{
    if(n ==0)
        return 1;       //实现了递归式的第一式,非递归的定义初始值
    return n*factorial(n-1);//实现了递归式的第二式
}

Fibonacci数列

Fibonacci(斐波那契)数列是一个生成规则非常简单,但是非常神奇的数列。具体有多神奇大家可以自己研究一下,我们今天探讨的内容是如何用递归的方式生成Fibonacci数列。它可以被递归地定义为

$$F(n)=\left\{\begin{matrix}
1 & n=0\\
1 & n=1\\
F(n-1)+F(n-2) &n>1
\end{matrix}\right.$$

Fibonacci数列的生成规则是:数列第一二位是自然数1,每一位都是前两位的和。例如1,1,2,3,5,8,13,21…。在递归式中,我们初始设定了两个非递归定义的初始值,然后用两个较小的自变量的函数值来定义一个较大自变量的函数值。F(n)表示Fibonacci数列中第n位的值,F(n)=F(n-1)+F(n-2)。那如何用函数来实现计算出数列中第n位的值呢?其实和阶乘一样非常简单。

int fibonacci(int i)
{
    if(n<=1)
        return 1;
    return fibonacci(n-1)+fibonacci(n-2);
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注