android-notes/blogs/Algorithm/剑指 Offer/递归相关.md

---
递归相关
---

#### [10- I. 斐波那契数列](https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/)

```java
class Solution {

    public int fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int start = 0;
        int end = 1;
        int result = 0;
        for (int i = 2; i <= n; i++) {
            result = (start + end) % 1000000007;
            start = end;
            end = result;
        }
        return result;
    }
}
```

#### [10- II. 青蛙跳台阶问题](https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/)

```java
class Solution {

    public int numWays(int n) {
        int result = 0;
        int start = 1;
        int end = 1;
        if (n == 0 || n == 1) {
            return 1;
        }
        for (int i = 2; i <= n; i++) {
            result = (start + end) % 1000000007;
            start = end;
            end = result;
        }
        return result;
    }
}
```