ACM之递归

ACM之递归

百度百科—递归

程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

百度百科—递归

程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

递归定义

递归,就是在运行的过程中调用自己。 构成递归需具备的条件: 函数嵌套调用过程示例 函数嵌套调用过程示例

  1. 子问题须与原始问题为同样的事,且更为简单;
  2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。 在数学和计算机科学中,递归指由一种(或多种)简单的基本情况定义的一类对象或方法,并规定其他所有情况都能被还原为其基本情况。 例如,下列为某人祖先的递归定义: 某人的双亲是他的祖先(基本情况)。某人祖先的双亲同样是某人的祖先(递归步骤)。斐波纳契数列(Fibonacci Sequence),又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21….. I [1] 斐波纳契数列是典型的递归案例: 递归关系就是实体自己和自己建立关系。 Fib(0) = 1 [基本情况] Fib(1) = 1 [基本情况] 对所有n > 1的整数:Fib(n) = (Fib(n-1) + Fib(n-2)) [递归定义] 尽管有许多数学函数均可以递归表示,但在实际应用中,递归定义的高开销往往会让人望而却步。例如: 阶乘(1) = 1 [基本情况] 对所有n > 1的整数:阶乘(n) = (n * 阶乘(n-1)) [递归定义] 一种便于理解的心理模型,是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如:你怎样才能移动100个箱子?答案:你首先移动一个箱子,并记下它移动到的位置,然后再去解决较小的问题:你怎样才能移动99个箱子?最终,你的问题将变为怎样移动一个箱子,而这时你已经知道该怎么做的。 如此的定义在数学中十分常见。例如,集合论对自然数的正式定义是:1是一个自然数,每个自然数都有一个后继,这一个后继也是自然数。 德罗斯特效应 德罗斯特效应 德罗斯特效应是递归的一种视觉形式。图中女性手持的物体中有一幅她本人手持同一物体的小图片,进而小图片中还有更小的一幅她手持同一物体的图片,依此类推。 又例如,我们在两面相对的镜子之间放一根正在燃烧的蜡烛,我们会从其中一面镜子里看到一根蜡烛,蜡烛后面又有一面镜子,镜子里面又有一根蜡烛……这也是递归的表现。

递归应用

依我看递归最经典的应用恐怕是斐波纳契数列,一个数等于前面两个数相加 例:求第n个斐波拉基数; 一般的算法:

#include<stdio.h>
int main(){
    int p1=1,p2=1,n,j=0;
    scanf("%d",&n);
    if(n>=3){
            printf("\n%d个斐波拉基数列:\n",n);
    for(int i=0;i<(n+1)/2;i++){
    printf("%d ",p1);
    j++;
    if(j!=n)
    printf("%d ",p2);
    p1=p1+p2;
    p2=p2+p1;
    j++;
    }
    }
    else{
        printf("输入的数字不够大");
    }

运用递归思想:

#include<stdio.h>
#include<iostream>
using namespace std;
int f(int n);
int main(){
    int n,sum;
cout <<"请输入一个数字"<<'\n';
    cin>> n;                        //输入一个整数n
sum=f(n);                         //函数调用
    cout<<sum<<'\n';
return 0;
}
int f(int n)
{
    if(n<=1)
        return n;
    else   
    return f(n-1)+f(n-2);//递归调用
}

栈和递归

#include<stdio.h>
#include<iostream>
using namespace std;
int f(int m){
    if(m==1) return 1;
    else {
        cout<<m<<endl;
        return f(m-1);
    }
} 
int main(){
    int n;
    int f(int m);
    cout<<"请输入一个大于1的数:"<<endl;
    cin>>n;
    cout<<f(n)<<endl;
    return 0;
}

经典题目:

1.一个人赶着鸭子去每个村庄卖,每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子,问他出发时共赶多少只鸭子?经过每个村子卖出多少只鸭子

题目分析:

递归终止的条件是当达到第7个村庄时递归停止,设经过的村庄数为n则有剩余的鸭子为总数为每次剩余的鸭子数位sum = sum-(sum/2+1) 算法构造:当 n=7 时 sum = 2;当 0<n<7 时 sum =2*m+2;

源代码:
#include <iostream.h>
class Questionone{
public: 
    int answer(int n, int sum){
        if(n>0){
            sum = 2*sum+2;    
            if(n-1>0){    
                cout<<"第"<<n-1<<"个村庄"<<"卖出"<<2*sum+2-sum<<endl;
            }
            n--;
            return answer(n,sum);
        
        }else{
            return sum;
        }
    }        
};
void main(){
    int SUM = 2;
    int  N =  7;
    Questionone question;
    cout<<"总数:"<<question.answer(N,SUM)<<endl;    
}

2.角谷定理

输入一个自然数,若为偶数,则把它除以2,若为奇数,则把它乘以3加1。经过如此有限次运算后,总可以得到自然数值1。求经过多少次可得到自然数1。 算法分析: 递归的终止条件是最后值为1;设输入的值为n先进项判断,若 n = 1则输出n; 若n不为1;则对他进行偶数判断,若为偶数除2,若为奇数则乘3加1;然后在进行偶数判断,直到n = 1为止; 算法构造 n=1 时 输出n;n!=1时 偶数判断 偶数 n = n/2;若是奇数 n = 3*n+1

源代码:
#include<iostream.h>
class questiontwo{
    public:
        int answer(int sum){
            if(sum == 1){
                cout<<" "<<sum;
                return sum;
            }else{
                if((sum%2) == 1){
                    sum = 3*sum+1;
                    cout<<" "<<sum;
                    return answer(sum);
                }else{
                    sum = sum/2;
                    cout<<" "<<sum;
                    return answer(sum);
                }
            }            
        }
};
void main(){
    int c ;
    cout<<"请输入一个数"<<endl;
    cin>>c;
    questiontwo question2;
    question2.answer(c);
}

3.电话号码

电话号码对应的字符组合:在电话或者手机上,一个数字对应着字母ABC,7对
应着PQRS。那么数字串27所对应的字符可能组合就有3*4种(如AP,BR等)。现
在输入一个3到11位长的电话号码,请打印出这个电话号码对应的字符的所有可
能组合和组合数。
题目分析:
根据题意可知:2对应的是ABC  3对应的是DEF 4对应的是GHI 5对应的JKL
6对应的是MNO 7对应的是PQRS 8对应的是TUV 9对应的是WXYZ
源代码:
public class questionthree {
    /**
    * 
    * @param number      电话号码
    * @param answer    辅助数组
    * @param index  电话位数中对应的第几位循环
    * @param n  电话位数
    */
    public static void Answer(int []number, int []answer,int 
    index,int n){
        char[][] word ={{},{},{'A','B','c'},{'D','E','F'},{'G',
            'H','I'},{'J','K','L'},{'M','N','O'},{'P','Q','R','s'},
            {'T','U','V'},{'W','X','Y','Z'}};
        int []sum = {0,0,3,3,3,3,3,4,3,4};
        if(index == n){
            for(int i = 0; i<n; i++){
                System.out.print(word[number[i]][answer[i]]);
            }
            System.out.println(";");
            return ;
        }
        for(answer[index] = 0; answer[index] < sum [number[index]]; answer[index]++){
            Answer(number,answer,index+1,n);
        }
    }
    public static void main(String[] args){
        int[] number = {2,3,4,5,6,7,8,9};
        int[] answer = new int[number.length];
        Answer(number, answer, 0, number.length);
        
    }
}

4.柿子分配:

日本著名数学游戏专家中村义作教授提出这样一个问题:父亲将2520个桔子分给六个儿子。分完 后父亲说:“老大将分给你的桔子的1/8给老二;老二拿到后连同原先的桔子分1/7给老三;老三拿到后连同原先的桔子分1/6给老四;老四拿到后连同原先的桔子分1/5给老五;老五拿到后连同原先的桔子分1/4给老六;老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一 样多。问六兄弟原来手中各有多少桔子?

题目分析:
解决此问题主要使用递归运算。由题目可以看出原来手中的加上得到的满足关系
式:StartNum = 420 * (n -2)/(n - 1) 分给下一个人的橘子数:
GiveNum = AfterGetNum / n;  下一个人的橘子数:nextStartNum = 420*
(n-1)/(n-2) - GiveNum;  下一个人加上之前得到的橘子的总数:
afterGetNum = nextStartNum + GiveNum;  以此使用递归算法可以算出各
个孩子原来手中的橘子数。
源代码:
public class questionfour {
    /**
    * 
    * @param n  表示第几个儿子
    * @param befor  表示为分配之前就的桔子数
    * @param After    表示分配之后的桔子数
    * @param m        分配的比例
    * @return
    */
    public int answer(int n,int befornum, int afternum,int m ){
        if(n>6){
            return 0;
        }else{
            System.out.println("老"+n+"原有的桔子数"+befornum);
            //分给下一个人的桔子数
            int givenum = afternum/m;
            //下一个人的桔子数
            int nextBeforenum = 420*(m-1)/(m-2)-givenum;
            //下一人加上之前的桔子数的总数
            int afterGetnum = nextBeforenum+givenum;
            return answer(n+1,nextBeforenum,afterGetnum,m-1);
        }
    }
    public static void main(String[] args){
        questionfour question4 = new questionfour();
        question4.answer(1, 240, 240, 8);
    }

来源:https://blog.csdn.net/qq_36102598/article/details/72055160

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 递归实现Ackman函数(C语言)

    Pain is only aware of their own has not changed only you know。痛不痛仅有自我明白,变没变仅有你明白...

    小Bob来啦
  • golang之递归

    超蛋lhy
  • Python之递归

    3.递归效率不高,递归层次过多会导致栈溢出(在计算机中,函数调用时通过栈(stack)这种结构数据实现的,每当进入一个函数调用栈就会多一层栈帧,每当函数返回,栈...

    py3study
  • Python之路_递归

    py3study
  • 算法之递归

    也就是递归一般会有一个判断,这是递归算法的出口(1 处);还有一个返回这个函数的执行结果(2 处);这两点是实现递归的关键。如果没有出口,递归就会变成死循环,而...

    多云转晴
  • 算法之递归

    递归是一种应用非常广泛的算法,在很多的数据结构和算法的编码中都会用到,理解递归是非常重要的。

    信安本原
  • 字符串展开(递归)- HDU 1274

    常用纱线的品种一般不会超过25种,分别可以用小写字母表示不同的纱线,例如:abc表示三根纱线的排列;重复可以用数字和括号表示,例如:2(abc)表示abcabc...

    ACM算法日常
  • 递归与尾递归

    在介绍递归与尾递归之前,我们来看看递归的定义:程序调用自身的编程技巧称为递归( recursion)

    踏浪
  • JavaScript函数之递归

    递归 递归的本质就是使用函数自身来解决问题的思路。 递归的定义(摘): 程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中...

    二十三年蝉
  • Python之递归函数

    Python之递归函数 好久没有更新内容了,也好久没有给大家打个招呼了,小白想死你们了。今天跟大家说说Python中的递归函数。 Python是支持递归函数的。...

    企鹅号小编
  • Python之递归函数

    Python之递归函数 好久没有更新内容了,也好久没有给大家打个招呼了,小白想死你们了。今天跟大家说说Python中的递归函数。 Python是支持递归函数的...

    1846122963
  • Python之递归函数

    递归函数 初识递归函数 递归函数的定义:在一个函数里再调用这个函数本身 Python为了考虑保护内存占用情况,有一个递归深度的限制。 探究递归的默认最大深度: ...

    新人小试
  • 递归与伪递归区别,Python 实现递归与尾递归

          递归函数在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函 数。(1) 递归就是在过程或函数里调用自身。(2) 在使...

    学到老
  • 递归与伪递归区别,Python 实现递归与尾递归

          递归函数在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函 数。(1) 递归就是在过程或函数里调用自身。(2) 在使...

    学到老
  • 了解递归:普通函数递归和非递归栈式实现之间的区别

    如果编译器编译上述的伪代码,那么在函数栈帧中会保存要返回的地址。在上述情景中,节点2的栈帧中不应该只保存节点2,应该还要保存2执行到第几行了。

    执生
  • 算法之递归案例

    杨充
  • 基本算法之-递归

    俗话说,大事化小。递归算法也是分治的思想。我国古代的愚公移山,就是这种递归。子又生孙,孙又生子。

    赵云龙龙
  • 递归之迷宫问题

    1.什么是递归? 简单来说,递归就是自己调用自己,每次调用自己都会创建新的栈帧。

    shengjk1
  • 漫谈递归转非递归

    一:递归的思想       之前面试腾讯,面试官问了一个问题:说说递归和循环的区别?当时没有答出问题的本质,只是简单地解释了这两个词的意思,囧,今天就借由这篇文...

    猿大白

扫码关注云+社区

领取腾讯云代金券