1.根据下面递归函数:调用函数Fun(2),返回值是多少( )
int Fun(int n) { if(n==5) return 2; else return 2*Fun(n+1); }
A.2
B.4
C.8
D.16
Fun(2)--->返回16 return 2*Fun(3) 2*8=16 |__Fun(3):8 return 2*Fun(4) 2*4=8 |__Fun(4):4 return 2*Fun(5) 2*2=4 |__Fun(5):2 return 2
2.关于递归的描述错误的是:( )
A.存在限制条件,当满足这个限制条件的时候,递归便不再继续
B.每次递归调用之后越来越接近这个限制条件
C.递归可以无限递归下去
D.递归层次太深,会出现栈溢出现象
答案解析:
递归的两个条件:
1. 将问题转化为其子问题,子问题要与原问题具有相同的解法
2. 递归的出口
A:正确,限制条件即递归的出口,如果限制条件满足,递归程序就可以退出了
B:正确,因为每次递归,都是将原问题进一步缩小,缩小到限制条件时,就可以往回返,直到第一次递归调用
比如:递归求和
C:错误,递归不能无限递归下去,否则会造成死循环和栈溢出
D:正确,因为每次递归,相当于都是一次新的函数调用,而每次函数调用系统必须给该函数划分栈帧空间,内部的递归函数没有退出,上层的递归就不能退出,栈帧就会累积许多块,如果累积超过栈的总大小,就会栈溢出。
3.计算斐波那契数
/* 思路: 一个问题直接求解时不好求解,如果可以将其划分成其子问题,并且子问题和原问题有相同的解法时,就可以使用递归的方式解决 递归的两个条件: 1. 将问题划分成其子问题,要求:子问题要与原问题具有相同的解法 2. 递归的出口 1 N < 3 Fac(N) Fac(N-1) + Fac(N-2) N >= 3 */ long long Fac(int N) { if(N < 3) return 1; return Fac(N-1) + Fac(N-2); }
4.递归实现n的k次方
/* 思路: 1 K==0 Pow(n,K) = Pow(n, K-1)*n */ int Pow(int n, int k) { if(k==0) return 1; else if(k>=1) { return n*Pow(n, k-1); } }
5.计算一个数的每位之和(递归实现)
例如,调用DigitSum(1729),则应该返回1+7+2+9,它的和是19 输入:1729,输出:19
/* 思路: n n < 10 DigiSum(n) = DibiSum(n/10)+n%10 // 前n-1位之和+第N位 */ int DigitSum(int n)//1729 { if(n>9) return DigitSum(n/10)+n%10; else return n; }
6.递归和非递归分别实现求n的阶乘(不考虑溢出的问题)
/* Fac(N) = 1*2*3*……*N 递归方式实现: 1 N <= 1 Fac(N) Fac(N-1)*N N >= 2 */ long long Fac(int N) { if(N <= 1) return 1; return Fac(N-1)*N; } /* 循环方式:从1乘到N即可 */ long long Fac(int N) { long long ret = 1; for(int i = 2; i <= N; ++i) { ret *= i; } return ret; }
7.递归方式实现打印一个整数的每一位
/* 思路: N N <= 9 Print(N) Print(N-1), 打印N */ void print(unsigned int n) { if(n>9) print(n/10); printf("%d ", n%10); }
8.将二进制数101011转换为十进制数时,其值是多少?
A.11
B.43
C.85
D.101
要将二进制数 101011 转换为十进制数,可以使用权重法来计算。
二进制数的每个位上的数字可以看作是一个权重为2的幂的系数。从右到左,权重的幂逐渐增加。
对于二进制数 101011,可以按照以下计算步骤转换为十进制数:
从右到左,将每个位数字与相应的权重相乘: 1 * 2^0 = 1 1 * 2^1 = 2 0 * 2^2 = 0 1 * 2^3 = 8 0 * 2^4 = 0 1 * 2^5 = 32
将所有乘积相加: 1 + 2 + 0 + 8 + 0 + 32 = 43
因此,二进制数 101011 转换为十进制数的值为 43。
9.将十六进制数3F转换为二进制数时,其结果是什么?
A.111111
B.001111
C.110011
D.111100
A 、111111