新春签到免费送会员,每天签到一次,送一天会员,活动截止时间不定,随时终止!机会不要错过哦!
首页  >   经验  >   C++递归总结(一)

C++递归总结(一)

烫烫烫烫烫烫烫烫 2018-12-18 17:59:42 1029
递归  
简介前面几天我更新关于递归调用这样一种简单操作,而递归程序设计是C++语言程序设计中的一种重要的方法,它使许多复杂的问题变得简单,容易解决了。

下面弄例题的方式来让大家深入理解递归

设有N个数已经按从大到小的顺序排列,现在输入X,判断它是否在这N个数中,如果存在则输出:“YES” 否则输出“NO”。

【算法分析】

       该问题属于数据的查找问题,数据查找有多种方法,通常方法是:顺序查找和二分查找,当N个数排好序时,用二分查找方法速度大大加快。二分查找算法:

   (1) 设有N个数,存放在A数组中,待查找数为X,用L指向数据的高端,用R指向数据的低端,MID指向中间:

   (2) 若X=A[MID] 输出 “YES”;

   (3)若X<A[MID]则到数据后半段查找:R不变,L=MID+1,计算新的MID值,并进行新的一段查找;

   (4) 若X>A[MID]则到数据前半段查找:L不变,R=MID-1,计算新的MID值,并进行新的一段查找;

    (5)若L>R都没有查找到,则输出“NO”。

    该算法符合递归程序设计的基本规律,可以用递归方法设计。 



参考代码如下:

#include<iostream>
#include<cstdlib>
using namespace std;
int a[11];
void search(int,int,int);
int main()   //主程序
{
    int k,x,L=1,R=10;
    cout<<"输入10个从大到小顺序的数:"<<endl;
    for (k=1;k<=10;k++)
        cin>>a[k];
    cin>>x;
    search(x,L,R); 
    system("pause");     
}
void search(int x,int top,int bot) //二分查找递归过程
{
    int mid; 
    if (top<=bot)
    {
        mid=(top+bot)/2;   //求中间数的位置
        if (x==a[mid]) 
            cout<<"YES"<<endl;     //找到就输出
    	else 
            if (x<a[mid])
                search(x,mid+1,bot);    //判断在前半段还是后半段查找
    	    else 
                search(x,top,mid-1);
    }  
    else 
        cout<<"NO"<<endl;
}


文章标题:C++递归总结(一)
文章地址:http://www.cjjjs.com/article/20151010175848804
转载到个人博客,请在文末带上右侧内容(含超链接):本文转载自:C++递归总结(一)
收藏 0 点赞 0

相关阅读

  1. 用递归算法求鸡兔问题
  2. 编程练习-用递归实现十六进制转二进制代码
  3. 关于递归在快速排序中的应用疑问
  4. 数据结构笔记分享:40 递归转换非递归
  5. MFC实现递归遍历文件夹内的所有文件夹和文件
  6. 数据结构笔记分享:8 二叉搜索树的迭代和递归查找
  7. 二叉树实现查找和统计个数、比较、求深度的递归
  8. 走台阶问题--递归问题
  9. C++递归总结(三)
  10. C++递归总结(二)
分享到:
分享文章[C++递归总结(一)]到QQ空间

相关阅读

  • 用递归算法求鸡兔问题

    C++技术网已经用心解答了用户提出的问题【用递归算法求鸡兔问题】,如还有问题,请继续在文章底部留言交流,直到完全懂了为止。

  • 编程练习-用递归实现十六进制转二进制代码

    很早之前写的小代码,分享出来。功能描述:十六进制转换为二进制,练习递归使用。

  • 关于递归在快速排序中的应用疑问

    C++技术网已经用心解答了用户提出的问题【关于递归在快速排序中的应用疑问】,如还有问题,请继续在文章底部留言交流,直到完全懂了为止。

  • 数据结构笔记分享:40 递归转换非递归

    一般根据是否需要回朔可以把递归分成简单递归和复杂递归,简单递归一般就是根据递归式来找出递推公式(这也就引申出分治思想和动态规划)。而复杂递归一就是模拟系统处理递归的机制,使用栈或队列等数据结构保存回朔点来求解。

  • MFC实现递归遍历文件夹内的所有文件夹和文件

    为了简化自己的工作,所以就用MFC快速做了递归遍历文件夹内所有文件夹和文件的功能。因为这个功能非常实用,非常有必要总结出来供大家参考。

  • 数据结构笔记分享:8 二叉搜索树的迭代和递归查找

    分享笔记的同时真的发现学习了很多,自己能再次复习一次,然后还有人指出了你理解的错误,弥补学习的漏洞。所以非常感激那些指出我错误的那些大神。

  • 二叉树实现查找和统计个数、比较、求深度的递归

    几个二叉树的性质首先要知道:每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒。 1、非空二叉树的第n层上至多有2^(n-1)个元素。 2、深度为h的二叉树至多有2^h-1个结点。 满二叉树:所有终端都在同一层次,且非终端结点的度数为2。 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1。 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置。

  • 走台阶问题--递归问题

    今天在一个面试题目看见了一个走台阶问题,感觉挺有趣的所以研究了一下,我他和大家一起分享。

  • C++递归总结(三)

    简单的例题,最后熟悉下一递归的含义

  • C++递归总结(二)

    Hanoi汉诺塔问题一直是递归的经典案例