单选题

若实现一个未加入任何优化的递归版本的斐波那契序列实现，该递归版本实现的时间...

Question

若实现一个未加入任何优化的递归版本的斐波那契序列实现，该递归版本实现的时间复杂度和空间复杂度是怎样的?(不考虑整数溢出和机器的内存限制）

A. 时间复杂度O(n)，
空间复杂度O(2^n)

B. 时间复杂度O(2^n), 空间复杂度O(n)

C. 时间复杂度O(n), 空间复杂度O(n)

D. 时间复杂度O(2^n), 空间复杂度O(2^n)