浅谈：算法中的斐波那契数（二）

解决方案

方法一：递归

使用递归计算给定整数的斐波那契数。

上图表示了 fib(5) 计算过程的递归树。

Java 实现

public class Solution { public int fib(int N) { if (N <= 1) { return N; } return fib(N-1) + fib(N-2); } }

Python 实现

class Solution: def fib(self, N: int) -> int: if N <= 1: return N return self.fib(N-1) + self.fib(N-2)

Go 实现

func fib(N int) int { if N <= 1 { return N } return fib(N-1) + fib(N-2) }

复杂度分析