递归思想介绍和案列


说明


本文我先写在我的CSDN上后再转到该博客系统的,有些链接会跳转我的CSDN上


递归的概念

递归算法:直接或间接地调用自身的算法。
递归函数:用函数自身给出定义的函数。
 使用递归技术使得算法的描述简捷且易于理解。


例1 阶乘函数

 阶乘函数可递归地定义为:

边界条件递归方程是递归函数的二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果。

 阶乘函数的递归调用算法:

int factorial(int n)
{
   if (n ==0) return 1;
   return n*factorial(n-1) ;
}



例2 Fibonacci数列

 无穷数列1,1,2,3,5,8,13,21,34,55,……,称为Fibonacci数列。它可以递归地定义为:

 第n个Fibonacci数可递归地计算如下:

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




 前2例中的函数都可以找到相应的非递归方式定义:

 但是,有的函数却无法找到非递归定义,比如Ackerman函数.


例3 Ackerman函数

  • n!趋向于正无穷的速度非常快,logn趋向无穷的速度则非常慢;
  • Ackerman函数:增长速度比n!快;比logn慢的多的函数;

 当一个函数及它的一个变量是由函数自身定义时,称这个函数是双递归函数

 Ackerman函数A(n,m)定义如下:

 A(n,m)的自变量m的每一个值都定义了一个单变量函数:

 (1)m=0,n≥2时,A(n,0)=n+2

 (2) m=1,n≥1时,A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2=A(A(n-2,1),0)+2=A(n-2,1)+2+2=…=A(1,1)+2(n-1),和A(1,1)=A(A(0,1),0)=A(1,0)=2, 故`A(n,1)=2n`

 (3) m=2时,A(n,2)=A(A(n-1,2),1)=2A(n-1,2)=…=2n-1A(1,2)和A(1,2)=A(A(0,2),1)=A(1,1)=2故A(n,2)=2n

 (4) m=3时,类似的可以推出
       

 (5) m=4时,A(n,4)的增长速度非常快,以至于没有适当的数学式子来表示这一函数


 定义单变量的Ackerman函数A(n)为,A(n)=A(n,n)。

 定义其拟逆函数α(n)为:

        α(n)= min{k|A(k)≥n}。

 α(n)是使A(k)≥n成立的最小的k值。

 如:A(0)=1,A(1)=2,A(2)=4和A(3)=16,可以得到α(1)=0,α(2)=1,α(3)=2,α(4)=2,α(5)=3‥ =α(16)=3

 α(n)在复杂度分析中常遇到。对于通常所见到的正整数n,有α(n)≤4

 理论上α(n)没有上界,随着n的增加,它以难以想象的慢速度趋向正无穷大。



例4 整数划分问题

 将正整数n表示成一系列正整数之和:

  • n=n1+n2+…+nk
  • 其中n1≥n2≥…≥nk≥1,k≥1。

 正整数n的这种表示称为正整数n的划分

求正整数n的不同划分个数

 例如正整数6有如下11种不同的划分:
    6;
    5+1;
    4+2,4+1+1;
   3+3,3+2+1,3+1+1+1;
   2+2+2,2+2+1+1,2+1+1+1+1;
   1+1+1+1+1+1。
 分析:前面的几个例子中,问题本身都具有比较明显的递归关系,易用递归函数直接求解。

 本例若设p(n)为正整数n的划分数,则难以找到递归关系。

 n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。

 现考虑增加一个自变量:将最大加数n1≤m的划分个数记作q(n,m)(n和,m为一个数)。q(n,m)有如下递归关系:

 (1) n≥1,m=1时,q(n,1)=1

  当最大加数n1 ≤ 1时,任何正整数n只有一种划分形式,即:
              

 (2) m≥n时,q(n,m)=q(n,n)

  最大加数n1实际上不能大于n。因此,q(1,m)=q(1,1)=1

 (3) m=n时,q(n,n)=1+ q(n,n-1)

  正整数n的划分由n1=n的划分和n1≤n-1的划分组成。

 (4) 1<m<n,q(n,m)=q(n,m-1)+w(n,m)
  其中q(n,m-1)为n1≤m-1的划分个数,w(n,m)为n1=m的划分个数

  正整数n的最大加数n1 ≤ m的划分,由n1≤m-1 的划分和n1=m的划分组成。

  注意:正整数n的n1=m的所有划分形式为n=m+m1+…+mi where m ≥m1 ≥m2 … ≥ mi ≥1

   That is, n-m =m1+…+mi

   因此,n的n1=m的划分个数是w(n,m)=q(n-m, m)

   因此,q(n,m)=q(n,m-1)+q(n-m, m)


q(n,m)递归关系:



例5 Hanoi塔问题

问题描述

 设A,B,C是3个塔座。开始时,在A上有n个圆盘,这些圆盘自下而上,由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n。

 问题:现要求将A上的这一叠圆盘移到B上,并仍按同样顺序叠置。

在移动圆盘时应遵守以下移动规则:

  • 规则1:每次只能移动1个圆盘;
  • 规则2:任何时刻都不允许将较大的圆盘压在较小的圆盘之上;
  • 规则3:在满足规则1,2的前提下,可将圆盘移至A,B,C中任一塔座上。

解题思路

    1. 将上面n-1个盘子从A座移到C座

    2. 将1个盘子(最底下的、最大的盘子)从A座移到B座

    3. 将n-1个盘子从C座移到B座


步骤

第一步:命令Y将n-1个盘子从A座移到C座

              将n-1个, 借助塔座B, 从A移动到到C



第二步:X自己将1个盘子(最底下的、最大的盘子)从A座移到B座。

               将1个从A移到B


第三步:再命令Y将个n-1盘子从C座移到B座。

                将n-1个,借助A, 从C移动到B

递归求解分析

 在问题规模较大时,较难找到一般的解法,因此用递归技术来解决这个问题。

  当n=1

   问题比较简单。只要将编号1的圆盘从塔座A直接移至塔座B上即可。


  当n>1时,

   用塔座B作为辅助,设法将n-1个较小的圆盘从塔座A移至C,然后,将剩下的最大圆盘从塔座A移至B。
   借助塔座A, 设法将n-1个较小的圆盘从塔座C移至B。


 由此可见,n个圆盘的移动问题可分为2次n-1个圆盘的移动问题,这又可以递归地用上述方法来做。

 Transfer(n,a,b,c)表示将塔座a由大到小叠在一起的n个圆盘,借助塔座c,按照规则移至塔座b上。

 Move(a,b)表示将塔座a上编号为n的圆盘移动到塔座b上。


算法

#include

using namespace std;


void move(char x,char y)
{
     cout<"<>n;
    transfer(n,'A','B','C');
    return 0;

}


测试样例

输入
5

输出
A——>B
A——>C
B——>C
A——>B
C——>A
C——>B
A——>B
A——>C
B——>C
B——>A
C——>A
B——>C
A——>B
A——>C
B——>C
A——>B
C——>A
C——>B
A——>B
C——>A
B——>C
B——>A
C——>A
C——>B
A——>B
A——>C
B——>C
A——>B
C——>A
C——>B
A——>B


递归小结

 优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性。因此,它为设计算法、调试程序带来很大方便。

 缺点:递归算法的运行效率较低,无论是耗费的计算时间,还是占用的存储空间,都比非递归算法要多。


文章作者: 小莫の咕哒君
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 小莫の咕哒君 !
评论
  目录