首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >递归函数及例题_递归树求解递归式例题

递归函数及例题_递归树求解递归式例题

作者头像
Java架构师必看
发布于 2022-07-19 00:34:37
发布于 2022-07-19 00:34:37
79000
代码可运行
举报
文章被收录于专栏:Java架构师必看Java架构师必看
运行总次数:0
代码可运行

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说递归函数及例题_递归树求解递归式例题,希望能够帮助大家进步!!!

定义:

一种计算过程,如果其中每一步都要用到前一步或前几步的结果,称为递归的。用递归过程定义的函数,称为递归函数,例如连加、连乘及阶乘等。凡是递归的函数,都是可计算的,即能行的 。

古典递归函数,是一种定义在自然数集合上的函数,它的未知值往往要通过有限次运算回归到已知值来求出,故称为“递归”。它是古典递归函数论的研究对象 。

条件:

1 递归出口即结束条件;

2 递推关系;

例题1:求任意正整数的逆置数

示例1:

输入

890

输出

解题思路:

1 递归出口: n=0时可结束

2 递推关系: 使用变量flag标记是否是最后一位数。如果最后一位数是0,则不输出,直接再次调用int_inverts(n/10,flag)函数。如果不是,修改flag的值,先输出,然后在调用int_inverts(n/10,flag)。

参考代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <iostream>
#include <bits/stdc++.h>
#include <string>

using namespace std;
//求正整数的逆置数
//递归求
//结束条件:
//递推关系:

void int_inverts(int n,int flag)
{ 
   
    if(n == 0) return ;
    if(n%10 == 0 &&flag == 0)
     { 
   
         int_inverts(n/10,flag);
     }
     else

       { 
   
         flag =1;
         cout<<n%10;
         int_inverts(n/10,flag);
       }
}
int main()
{ 
   

    int n;
    cin>>n;
    int_inverts(n,0);
    cout<<endl;
}

只听到从架构师办公室传来架构君的声音:

尚寐无觉!有兔爰爰,雉离于罿。有谁来对上联或下联?

例题2:求最大公约数

题目描述

设计递归函数;计算正整数a和b的最大公约数并返回

输入与输出要求:

输入两个正整数a和b,输出两数的最大公约数数,占一行。

Sample 1:

Sample 2:

解题思路:

利用辗转相除法可知,当n%m!=0时,就一直计算(m,n%m)的最大公约数。可知

递归出口: n%m == 0 ,返回m;

递推关系: divisor(n,m) = divisor(m,n%m),当n%m != 0时;

参考代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
此代码由Java架构师必看网-架构君整理
#include <iostream>
#include <bits/stdc++.h>
#include <string>

using namespace std;
//求最大公约数
int divisor(int n,int m)
{ 
   
    if(n%m == 0) return m;
    return divisor(m,n%m);


}
int main()
{ 
   
    int n,m;
    cin>>n>>m;
    cout<<divisor(n,m)<<endl;
    return 0;
}

例题3:二进制转十进制数

问题描述:

输入一个整数n,代表二进制数,其长度不大于10,输出转换后的十进制数,占一行。

解题思路:

递归出口: n=1或n=0 , 直接返回值n;

地推关系: b_shift_d(n) = n%10 + 2*b_shift_d(n/10);

示例1:

示例2:

参考代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>

using namespace std;
//二进制数转十进制
int b_shift_d(int n)
{ 
   

    if(n == 0 || n == 1) return n;
    else
    { 
   
         return n%10+b_shift_d(n/10)*2;

    }
}
int main()
{ 
   
    int n;
    cin>>n;
    cout<<b_shift_d(n)<<endl;
    return 0;


}

例题4: 素数分解

问题描述:

素数,又称质数,是指除 1和其自身之外,没有其他约数的正整数。例如 2、3、5、13 都是质 数,而 4、9、12、18 则不是。 虽然素数不能分解成除 1和其自身之外整数的乘积,但却可以分解成更多素数的和。你需要编程 求出一个正整数最多能分解成多少个互不相同的素数的和。 例如,21 = 2 + 19 是 21的合法分解方法。21 = 2 + 3 + 5 + 11 则是分解为最多素数的方法。

输入 n (10 ≤ n ≤ 200)。

输出 n 最多能分解成多少个不同的素数的和。

样例1,

样例2,

解题思路:

先设置num[]数组来存储小于n的所有素数。其次,index即元素的下标,sum即元素之和,total为已经选择的元素的个数,作为递归函数的参数参与。可采用两种写法:

如下所示:

第一种:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
此代码由Java架构师必看网-架构君整理
int total = 0void find_longest(int index,int sum,int n)
{ 
   

     if(sum == n )
     { 
   
         if(longest < total)
            longest = total ;
         return ;
     }
     if(sum > n || index >= top)
        return ;
     total++;
     find_longest(index+1,sum+num[index],n);
     total--;
     find_longest(index+1,sum,n);

}

第二种:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
void find_longest(int index,int sum,int total,int n)
{ 
   

     if(sum == n )
     { 
   
         if(longest < total)
            longest = total ;
         return ;
     }
     if(sum > n || index >= top)
        return ;
     find_longest(index+1,sum+num[index],total+1,n);
     find_longest(index+1,sum,total,n);

}

参考代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
using namespace std;
//素数分解
/* 递归出口设定: 递推关系: */
int top=0;
int num[201];
int longest;

int is_prime(int n)
{ 
   
    if(n == 1) return 0;
    if(n == 2) return 1;
    for(int i=2;i<n;i++)
    { 
   
        if(n%i == 0)
        { 
   
            return 0;
            break;
        }
    }
    return 1;
}

void find_longest(int index,int sum,int total,int n)
{ 
   

     if(sum == n )
     { 
   
         if(longest < total)
            longest = total ;
         return ;
     }
     if(sum > n || index >= top)
        return ;
     find_longest(index+1,sum+num[index],total+1,n);
     find_longest(index+1,sum,total,n);

}
int main()
{ 
   

    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    { 
   

        if(is_prime(i))
            num[top++] = i;
    }
    longest = 0;
    find_longest(0,0,0,n);
    cout<<longest<<endl;
    return 0;
}

问题5:汉诺塔问题

题目描述:

n个圆盘从下面开始按大小顺序摆放在A柱子上。并且规定,任何时候,在小圆盘上都不能放大圆盘,且在三根柱子之间一次只能移动一个圆盘,求最少的移动步骤。

解题思路: (在链接中)

汉诺塔问题解题思路及代码

问题6:全排列问题:

对于给定的集合A{a1,a2,…,an},其中的n个元素互不相同,如何输出这n个元素的所有排列(全排列)。

解题思路:

全排列问题解题思路及代码

问题7: 整数划分问题:

问题描述:

整数划分问题是算法中的一个经典命题之一,有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分,是指把一个正整数n写成如下形式:

n=m1+m2+…+mi; (其中mi为正整数,并且1 <= mi <= n),则{m1,m2,…,mi}为n的一个划分。

1

正整数6有如下11种不同的划分,所以P(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

解题思路:

整数划分解题思路及代码

今天文章到此就结束了,感谢您的阅读,Java架构师必看祝您升职加薪,年年好运。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-07-182,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
算法基础学习笔记——⑭欧拉函数\快速幂\扩展欧几里得算法\中国剩余定理
在C语言中,可以使用算法来计算欧拉函数(Euler's Totient Function)。欧拉函数,也被称为φ函数,用于计算小于或等于给定数字n的正整数中与n互质的数的个数。
命运之光
2024/03/20
2850
算法基础学习笔记——⑭欧拉函数\快速幂\扩展欧几里得算法\中国剩余定理
洛谷P1306 斐波那契公约数
题目描述 对于Fibonacci数列:1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题:第n项和第m项的最大公约数是多少? 输入输出格式 输入格式: 两个正整数n和m。(n,m<=10^9) 注意:数据很大 输出格式: Fn和Fm的最大公约数。 由于看了大数字就头晕,所以只要输出最后的8位数字就可以了。 输入输出样例 输入样例#1: 4 7 输出样例#1: 1 说明 用递归&递推会超时 用通项公式也会超时 扩展欧几里得有一个非常重要的性质 1 #inc
attack
2018/04/11
7380
数学算法那些事
时间复杂度:最坏情况他们的最大公约数是1,循环做了t-1次,最好情况是只做了1次,可以得出O(n)=n/2;
黄规速
2022/04/14
3160
C++17 中的 std::gcd:探索最大公约数的现代 C++ 实现
在数学和编程中,最大公约数(GCD,Greatest Common Divisor)是一个非常重要的概念。它表示两个或多个整数共有约数中最大的一个。在 C++17 中,标准库引入了 std::gcd 函数,这使得计算最大公约数变得更加简单和高效。本文将详细介绍 std::gcd 的使用方法、实现原理以及一些实际应用场景。
码事漫谈
2025/02/12
6370
C++17 中的 std::gcd:探索最大公约数的现代 C++ 实现
golang刷leetcode 数学(1) 丑数系列
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
golangLeetcode
2022/08/02
2320
C++数学与算法系列之初等数论
在日常生活中,数通常出现在标记(如公路、电话和门牌号码)、序列号和编码上。在数学里,数的定义延伸至包含如分数、负数、无理数、超越数及复数等抽象化的概念。
一枚大果壳
2022/12/20
4380
C++数学与算法系列之初等数论
[重学Python]Day3 函数和模块的使用
为了解决重复代码的问题,我们可以封装重复的代码到“函数”的功能模块中,在需用使用该功能的地方,我们只需要“调用”这个“函数”就可以了。
李鹏华
2024/04/20
1920
c++学习总结(二)——递归函数
关于函数之前有过总结,函数是在编程中为简化主程序、使复杂程序简单化的子程序。而递归函数则是一种特殊的函数。它是直接或间接调用的函数,通常可以把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可以描述出解题过程所需要的多次重复计算。大大减少了程序的代码量。递归的能力在于有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分间接易懂。总而言之,使用递归函数是解决大型复杂问题必不可少的。
用户7886150
2021/02/05
7140
2022_HAUE_计算机学院暑期培训——扩展欧几里得算法
求 100 和18 两个正整数的最大公约数,用欧几里得算法,是这样进行的: 100 / 18 = 5 (余 10) 100%8=10 18 / 10= 1(余8) 18%10=8 10 / 8 = 1(余2) 10%8=2 8 / 2 = 4 (余0) 8%2=0 至此,最大公约数为2 以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 100 和 18 的最大公约数2。
浪漫主义狗
2022/09/16
7560
2022_HAUE_计算机学院暑期培训——扩展欧几里得算法
C语言经典习题100例(四)16-20
给大家介绍一堂Python入门课https://www.bilibili.com/video/BV1RZ4y1n75v,感觉还不错,适合初学者入门。
cutercorley
2020/07/23
5280
[重学Python]Day3 函数和模块的使用
项目链接:https://github.com/jackfrued/Python-100-Days
李鹏华
2024/04/15
2150
11.09作业详解(弹球距离,素数,最大公约数最小公倍数,求整数位数及其各位数字之和,打印乘法表)
代码比较简洁但并不容易理解,首先函数递归要有一个限制条件,且想办法然函数中的某个形参无限逼近与该条件,由题目可知,这个限制条件是让h*p^n逼近与0.001即可,当h*p^n满足小于0.001时返回h*p^(n-1),然后再往前推直到求到第一个dist函数,需要注意的是每次x与h的关系,第一次x=h*p,第二次传递x=h1*p,这时的h1由于第一次赋值等于h*p...然后一直往后递推直到x<0.001后返回,假设h*p^3<0.001,这时返回h*p^2,由于h*p^2>0.001,返回h+h*p^2+h*p^2...直到返回到第一次调用的dist函数即可。
一枕眠秋雨
2024/03/11
1430
11.09作业详解(弹球距离,素数,最大公约数最小公倍数,求整数位数及其各位数字之和,打印乘法表)
U10783 名字被和谐了
题目背景 众所周知,我们称g是a的约数,当且仅当g是正数且a mod g = 0。 众所周知,若g既是a的约数也是b的约数,我们称g是a、b的一个公约数。 众所周知,a、b最大的那个公约数就叫最大公约数。 题目描述 现在对于给定的两个正整数a、b,你需要求出它们次大的公约数(second greatest common divisor)。 输入输出格式 输入格式: 第一行两个正整数数a、b。 输出格式: 第一行一个数,表示a、b的次大公约数。若a、b的公约数只有一个,则输出-1。 输入输出
attack
2018/04/12
5740
数据结构与算法-求取两个整数的最大公约数
定理:两个正整数 a、b (a>b),它们的最大公约数等于 a 除以 b 的余数 c 和 b 之间的最大公约数
机器视觉CV
2019/11/14
7300
《程序员数学:素数》—— 你真的了解 RSA 加密算法吗?
作者:小傅哥 博客:https://bugstack.cn ❝沉淀、分享、成长,让自己和他人都能有所收获!😜 ❞ 一、什么是素数 二、对称加密和非对称加密 三、算法公式推导 四、关于RSA算法 五、实现RSA算法 1. 互为质数的p、q 2. 乘积n 3. 欧拉公式 φ(n) 4. 选取公钥e 5. 选取私钥d 6. 加密 7. 解密 8. 测试 六、RSA数学原理 1. 模运算 2. 最大公约数 3. 线性同余方程 4. 中国余数定理 5. 费马小定理 6. 算法证明 七、常见面试题 ----
小傅哥
2022/12/13
2.9K0
《程序员数学:素数》—— 你真的了解 RSA 加密算法吗?
20190108-使用递归函数实现求最大
1. 给定a = [1,2,[3,4,[5,6,7,[8,9,[10,11]]]]],要求打印输出:1,2,3,4,5,6,7,8,9,10,11
py3study
2020/01/19
6470
C语言经典编程题100例 11~20
11、题目:古典问题(兔子生崽):有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?(输出前40个月即可)
C you again
2022/08/22
2.3K0
C语言经典编程题100例 11~20
C语言求最小公倍数和最大公约数三种算法(经典)
最小公倍数:数论中的一种概念,两个整数公有的倍数成为他们的公倍数,其中一个最小的公倍数是他们的最小公倍数,同样地,若干个整数公有的倍数中最小的正整数称为它们的最小公倍数,维基百科:定义点击打开链接 求最小公倍数算法: 最小公倍数=两整数的乘积÷最大公约数 求最大公约数算法: (1)辗转相除法 有两整数a和b: ① a%b得余数c ② 若c=0,则b即为两数的最大公约数 ③ 若c≠0,则a=b,b=c,再回去执行① 例如求27和15的最大公约数过程为: 27÷15 余1215÷12余312÷3余0因此,3即为
Angel_Kitty
2018/04/08
4.7K0
【C语言程序设计——循环程序设计】求解最大公约数(头歌实践教学平台习题)【合集】
在这个代码中,gcd函数接受两个整数a和b。首先检查b是否为 0,如果是,那么a就是最大公约数,直接返回a。否则,递归调用gcd函数,将b和a % b作为新的参数传递进去。这个递归过程会不断进行,直到b变为 0,此时就找到了最大公约数。
Rossy Yan
2025/01/02
1340
【C语言程序设计——循环程序设计】求解最大公约数(头歌实践教学平台习题)【合集】
C语言初阶小练习1(1.素数的打印,2.闰年的判断和打印,3.求解两个数的最大公约数)
"试除",就是不断地尝试能否整除。比如要判断自然数 x 是否质数,就不断尝试小于 x 且大于1的自然数,只要有一个能整除,则 x 是合数;否则,x 是素数。
折枝寄北
2024/11/19
1100
C语言初阶小练习1(1.素数的打印,2.闰年的判断和打印,3.求解两个数的最大公约数)
推荐阅读
相关推荐
算法基础学习笔记——⑭欧拉函数\快速幂\扩展欧几里得算法\中国剩余定理
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验