递归题目.docx

递归题目.docx

《递归题目.docx》由会员分享，可在线阅读，更多相关《递归题目.docx（14页珍藏版）》请在冰点文库上搜索。

递归题目

例题

计算n的阶乘

#include 

intfactorial（intn）

{

  intresult;

  if（n<0）                     //判断例外

  {

    printf（"输入错误!

\n"）;

    return0;

  }elseif（n==0||n==1）

        {

          result=1; //回推墙

        }

      else

        {

          result=factorial（n-1）*n; //递推关系，这个数与上一个数之间的关系。

        }

  returnresult;

}

intmain（）{

  intn=5;                       //输入数字5，计算5的阶乘

  printf（"%d的阶乘=%d",n,factorial（n））;

  return0;

}

程序在计算5的阶乘的时候，先执行递推，当n=1或者n=0的时候返回1，再回推将计算并返回。

由此可以看出递归函数必须有结束条件。

递归函数特点：

    1. 每一级函数调用时都有自己的变量，但是函数代码并不会得到复制，如计算5的阶乘时每递推一次变量都不同；

    2. 每次调用都会有一次返回，如计算5的阶乘时每递推一次都返回进行下一次；

    3. 递归函数中，位于递归调用前的语句和各级被调用函数具有相同的执行顺序；

    4. 递归函数中，位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反；

    5. 递归函数中必须有终止语句。

一句话总结递归：

自我调用且有完成状态。

例题

小明为了学好英语，需要每天记单词，第一天记1个，第二天记2个依次类推，请用代码完成，算出小明第10天开始的时候会了多少个单词？

分析：

回推墙是“第一天记1个”

递推关系是“第n天记的单词=第n-1天记的单词数量+n"

#include

/*定义获取单词数量的函数*/

intgetWordNumber（n）

{  

  if（n==1）

  {

    return1;  //回推墙

  }

  else{

    returngetWordNumber（n-1）+n;   //递推关系

  }

}

intmain（）

{

  intnum=getWordNumber（10）;  //获取会了的单词数量

  printf（"小明第10天记了:

%d个单词。

\n",num）;

  return0;

}

例题

有5个人坐在一起，问第5个人多少岁？

他说比第4个人大2岁。

问第4个人岁数，他说比第3个人大2岁。

问第3个人，又说比第2人大两岁。

问第2个人，说比第1个人大两岁。

最后问第1个人，他说是10岁。

请问第5个人多大？

程序分析：

利用递归的方法，递归分为回推和递推两个阶段。

要想知道第5个人岁数，需知道第4人的岁数，依次类推，推到第1人（10岁），再往回推。

#include

/*

 *请使用递归函数完成本题

 *小编已将正确代码放在左侧任务的“不知道怎么办”里

 *小编希望各位童鞋独立完成哦~

 */

//定义一个函数，传送人员序号进去，返回该序号员工的年龄。

intgetAge（numPeople）

{

  //定义返回的年龄

  intage;

  //如果是第1个人的时候，年龄为10岁

  if（numPeople==1）

    age=10; //这是回推墙，也就是结束递归的条件。

  else

    //还没接触到回推墙，就自我调用，谓之递归。

    age=getAge（numPeople-1）+2; //年龄等于上一个人的年龄加2

  returnage;

}

intmain（）

{

 printf（"第5个人的年龄是%d岁",getAge（5））;

 return0;

} 

例题

猴子第一天摘下N个桃子，当时就吃了一半，还不过瘾，就又多吃了一个。

第二天又将剩下的桃子吃掉一半，又多吃了一个。

以后每天都吃前一天剩下的一半零一个。

到第10天在想吃的时候就剩一个桃子了,问第一天共摘下来多少个桃子？

并反向打印每天所剩桃子数。

#include

//定义一个函数，输入第n天，返回该天剩下的桃子数

intgetPeachNumber（n）

{

  intnum;  //定义所剩桃子数

  if（n==10）

  {

    num=1;   //递归结束条件，即回推墙

    returnnum;

  }

  else

  {

    num=（getPeachNumber（n+1）+1）*2; //递推关系

    printf（"第%d天所剩桃子%d个\n",n,num）;//天数，所剩桃子个数

  }

  returnnum;

}

intmain（）

{

  intnum=getPeachNumber

（1）;

  printf（"猴子第一天摘了:

%d个桃子。

\n",num）;

  return0;

}

递归（recursion）：

程序调用自身的编程技巧。

 递归满足2个条件：

   1）有反复执行的过程（调用自身）

   2）有跳出反复执行过程的条件（递归出口）

递归例子：

（1）阶乘

        n!

=n*（n-1）*（n-2）*...*1（n>0）

//阶乘

intrecursive（inti）

{

intsum=0;

if（0==i）

return

（1）;

else

sum=i*recursive（i-1）;

returnsum;

}

（2）河内塔问题

//河内塔

voidhanoi（intn,intp1,intp2,intp3）

{

if（1==n）

cout<<"盘子从"<

else

{

hanoi（n-1,p1,p3,p2）;

cout<<"盘子从"<

hanoi（n-1,p2,p1,p3）;

}

}

（3）全排列

 从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。

当m=n时所有的排列情况叫全排列。

 如1,2,3三个元素的全排列为：

 1,2,3

 1,3,2

 2,1,3

 2,3,1

 3,1,2

 3,2,1 

//全排列

inlinevoidSwap（int&a,int&b）

{

inttemp=a;

a=b;

b=temp;

}

voidPerm（intlist[],intk,intm）

{

if（k==m-1）

{

for（inti=0;i

{

printf（"%d",list[i]）;

}

printf（"n"）;

}

else

{

for（inti=k;i

{

Swap（list[k],list[i]）;

Perm（list,k+1,m）;

Swap（list[k],list[i]）;

}

}

}

（4）斐波那契数列

 斐波纳契数列，又称黄金分割数列，指的是这样一个数列：

1、1、2、3、5、8、13、21、……

 这个数列从第三项开始，每一项都等于前两项之和。

 有趣的兔子问题：

 一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。

如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

 分析如下：

 第一个月小兔子没有繁殖能力，所以还是一对；

 两个月后，生下一对小兔子，总数共有两对；

 三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，总数共是三对；

 ……　

 依次类推可以列出下表：

//斐波那契

longFib（intn）

{

 if（n==0） 

  return0;

 if（n==1） 

  return1;

 if（n>1） 

  returnFib（n-1）+Fib（n-2）;

}

（4）判定一系列字符串中是否有相同的内容

publicclassT{

publicstaticvoidmain（String[]args）{

String[]a={"a1","a2","a3","b3","c","b","33","33"};

booleanb=newT（）.fun（0,a）;

System.out.println（b）;

}

publicbooleanfun（intn,String[]a）{

booleanb=false;

if（n==a.length）{

b=true;

}else{

for（inti=n;i

System.out.println（n+""+（i+1））;

if（a[n].equals（a[i+1]））{

returnfalse;

}

}

n++;

fun（n,a）;

}

returnb;

}

}

1.Fibonacci数

我们直到Fibonacci数的递推公式为：

F（0）=F

（1）=1,F（n）=F（n-1）+F（n-2）n>=2;

这个明显地给出了递归边界n=0或1的时候F（n）的值，和递归逻辑F（n）=F（n-1）+F（n-2），即递推公式.所以这个递归函数不难书写

intF（intn）//函数返回一个数对应的Fibonacci数

2.阶乘

阶乘的递归公式为：

3.数组求和

给一个数组a[]:

a[0],a[1],...,a[n-1]如何用递归的方式求和？

仍然是两个问题：

递归边界和递归公式.

递归边界是什么？

一时不容易想到，但是我们想到了求和，多个数的求和过程是什么，x,y,z,w手动求和的过程是什么？

步骤如下：

x+y=a,任务变为a,z,w求和

a+z=b,任务变为b,w求和

b+w=c得出答案

思考一下，【得出答案】这一步为什么就可以得出答案呢？

（废话？

）是因为，一个数不用相加就能得出答案.

所以，递归的边界就是只有一个数.

所以，递归边界有了，那么递归公式呢？

其实手动计算过程中，隐含了递归公式：

其中+为求两个数的和，F为求多个数的和的递归函数.代码如下：

#include

usingnamespacestd;

intF（inta[],intstart,intend）

{

if（start==end）//递归边界

returna[start];

returna[start]+F（a,start+1,end）;//递归公式

}

intmain（）

{

inta[]={1,2,3,4,5};

ints=0,e=4;

cout<

return0;

}

4.求数组元素最大值

手动求最大值的过程是什么，遍历+比较，过程如下：

例如，求3,2,6,7,2,4的最大值：

先设置最大值max=-999999，然后将max和数组元素逐个（遍历）比较如果a[i]>max，则更新max的值为a[i]，否则max不变，继续向后遍历，直到遍历结束.

max<3，则max=3

max>2，max=3不变

max<6，则max=6

max<7，则max=7

max>2，max=7不变

max>4，max=7不变

遍历结束，max=7为最大值.

和求和类似，递归的公式如下：

其中max为求两个数的较大值函数，F为求多个数的最大值的递归函数.代码如下：

#include

usingnamespacestd;

#definemax（a,b）（a>b?

a:

b）

intF（inta[],ints,inte）

{

if（s==e）

returna[s];

elseif（s+1==e）//递归边界

returnmax（a[s],a[e]）;

returnmax（a[s],F（a,s+1,e））;//递归公式!

!

!

}

intmain（）

{

inta[]={5,1,4,6,2};

ints=0,e=4;

cout<

return0;

}

之所以，说上面的几个例子是【简单例子】，是因为上述所有的递归都属于【单向递归】.单向递归，递归的路径就是一个方向，所以思路相对比较容易想到.

-