数据结构 - 算法面试题之一

算法

递归

递归的三大要素:

  • 第一要素:明确递归函数想要干什么
  • 第二要素:寻找递归的结束条件
  • 第三要素:找出递归函数的等价关系式

递归的优缺点:

  • 递归中很多计算都是重复的,由于其本质是把一个问题分解成两个或者多个小问题,多个小问题存在相互重叠的部分,则存在重复计算
  • 调用栈可能会溢出,其实每一次函数调用会在内存栈中分配空间,而每个进程的栈的容量是有限的,当递归的层次太深时,就会超出栈的容量,从而导致栈溢出
  • 递归由于是函数调用自身,而函数调用是有时间和空间的消耗的;每一次函数调用,都需要在内存栈中分配空间以保存参数、返回地址以及临时变量,而往栈中压入数据和弹出数据都需要时间,导致运行效率较低
  • 递归与循环相比,循环的代码可读性不如递归,但运行效率更高

案例分析:

一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级,求该青蛙跳上一个 N 级的台阶总共有多少种跳法?

  • 每次跳的时候,小青蛙可以跳一个台阶,也可以跳两个台阶,也就是说,每次跳的时候,小青蛙有两种跳法
  • 第一种跳法:第一次跳了一个台阶,那么还剩下 n-1 个台阶还没跳,剩下的 n-1 个台阶的跳法有 f (n-1) 种
  • 第二种跳法:第一次跳了两个台阶,那么还剩下 n-2 个 台阶还没跳,剩下的 n-2 个台阶的跳法有 f (n-2) 种
  • 所以,小青蛙的全部跳法就是这两种跳法之和,即 f (n) = f (n-1) + f (n-2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Example {

public static void main(String[] args) {
int count = f(3);
System.out.println(count);
}

public static int f(int n) {
if (n <= 2) {
return n;
}
return fn(n - 1) + fn(n - 2);
}

}