0%

面试题-递归

上周的一道笔试题

递归计算

根据两组参数,使用递归完成编程。

递归方法

​ 参数1 [1,3]

​ 参数2 n

当参数2 < 小于参数1中元素个数的时候,不输出。

当n = 3 时 输出 [1,3,4]

当n = 4 时 输出 [1,3,4,7]

当 n = 11 使用递归程序输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void test(List<Integer> list , Integer end) {
if(list.isEmpty() || list.size() < 1 || end == null || end < 0){
throw new RuntimeException("初始化参数异常");
}
if (list.size() < end) {
int length = list.size();
list.add(list.get(length - 1) + list.get(length - 2));
test(list , end);
}
}

public static void main(String[] args) {
Integer[] arr = new Integer[]{1,3};
List<Integer> list = new ArrayList(Arrays.asList(arr));
test(list , 11);
System.out.println(list.toString());
}

>>
[1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199]

不过当时写的时候并没有判断异常。当时紧张硬编码。

古典问题:⼀对兔⼦

有⼀对兔⼦,从出⽣后第 3 个⽉起每个⽉都⽣⼀对兔⼦,⼩兔⼦⻓到第三个⽉后每个⽉⼜⽣⼀对兔⼦,

假如兔⼦都不死,问每个⽉的兔⼦对数为多少?

思路:斐波那契数列(Fibonacci sequence)

程序分析: 兔⼦的规律为数列 1,1,2,3,5,8,13,21…,当 n=1 或 n=2时,分别为 1。

从 n=3 开始 f(n) = f(n-1) + f(n-2)。所以转化为程序则如下:

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
int n = 10;
System.out.println("第" + n + "个⽉兔⼦总数为" + fun(n));
}
private static int fun(int n) {
if (n == 1 || n == 2)
return 1;
else
return fun(n - 1) + fun(n - 2);
}

使⽤递归实现 n! 的阶乘

思路:求⼀个数的阶乘,既可以使⽤循环,也可以使⽤递归。本地要求使⽤递归。

把公式分解后 n! = n*(n-1)! ;但是 1的阶乘为 1。所以我们可以定义⼀个⽅法 jie(int n),假定⽅法就是

求阶乘的⽅法,则每次 n! = n * jie(n-1)。这样就实现了⽅法逻辑了。

1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {
int n = 10;
System.out.println(n+"阶乘为:" + jie(n));
}
private static int jie(int n) {
if(n==1) {
return 1;
}else {
return n*jie(n-1);
}
}

⽤递归实现字符串倒转

思路:字符串倒序可以有多种实现⽅法,但是本地要求递归。所以我们需要找出相同的可以重复的⽅法来递归完成。

例如:“hello”

  • 第⼀次:截取第⼀个字符“h”,截取剩下“ello”,使⽤“ello”+“h”;

  • 第⼆次:那么“ello”字符串,可以使⽤相同的⽅法,“llo”+“e”;

  • 第三次:“lo”+“l”;

  • 第四次:“o”+“l”;

  • 第五次:“o”⻓度已经是⼀个了,所以依次返回给上⼀步“olleh”。

1
2
3
4
5
6
7
8
9
10
11
public class StringReverse {
public static String reverse(String originStr) {
if(originStr == null || originStr.length()== 1) {
return originStr;
}
return reverse(originStr.substring(1))+ originStr.charAt(0);
}
public static void main(String[] args) {
System.out.println(reverse("hello"));
}
}