算法思想篇递归

1.什么情况下使用递归

　　可以将一个问题分解为很多子问题

　　这个问题的求解思路与子问题的思路完全一样

　　有递归的终止条件

2.斐波那契

package com.jun.algorithm.foundation.thought;
import org.junit.Test;
/**
* 斐波那契
* 递归的条件：
* 一个问题可以分为几个子问题
* 子问题的求解思路都是完全一样
* 存在递归的终止条件
*

* 这里将会一步步的优化
* 先递归，然后循环，然后使用缓存，最后使用尾递归方式
*/
public class Fibonacci {
/**
* 递归方式
* 时间复杂度：2^n
*/
public int fab(int n) {
if (n <= 2) {
return 1;
}
return fab(n - 1) + fab(n - 2);
}
/**
* 循环
* 时间复杂度 n
*
* @param n
*/
public int noFab(int n) {
if (n <= 2) {
return 1;
}
int a = 1;
int b = 1;
int c = 0;
for (int i = 3; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
private int[] data = new int[6];
/**
* 使用缓存，计算过的不在计算了
*/
public int fabWithArray(int n) {
if (n <= 2) {
return 1;
}
if (data[n] > 0) {
return data[n];
}
int result = fabWithArray(n - 1) + fabWithArray(n - 2);
data[n] = result;
return result;
}
/**
* 尾递归
* 倒着算
* 传递结果
* preResult:上次的结果
* result：当前的结果
*

* 尾递归的条件：
* 最后的返回，不要再做任何的操作
*/
public int tailFab(int n, int preResult, int result) {
if (n <= 2) {
return result;
}
// 传递下去，再做一步计算
return tailFab(n - 1, result, preResult + result);
}
@Test
public void test() {
int fab = fab(6);
int noFab = noFab(6);
System.out.println("noFab=" + noFab);
System.out.println("fab=" + fab);
int i = tailFab(6, 1, 1);
System.out.println("fabWithArray=" + i);
}
}