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

发表于 阅读次数： 评论数： 本文字数： 555 阅读时长 ≈ 1 分钟

算法

递归

递归的三大要素：

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

递归的优缺点：

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

案例分析：

一只青蛙一次可以跳上 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);
	}

}