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
