CSP-S 2024 第一轮 第6题：根据递推关系计算函数值

题目

已知 $f(1) = 1$，且对于 $n \geq 2$ 有 $f(n) = f(n - 1) + f(\lfloor n/2\rfloor )$，则 $f(4)$ 的值为？

选项

• A. 4
• B. 5
• C. 6
• D. 7

答案

B

题解

从 $f(1)=1$ 开始，依次代入递推式（$\lfloor n/2\rfloor$ 表示向下取整）：

• $f(2)=f(1)+f(1)=1+1=2$
• $f(3)=f(2)+f(1)=2+1=3$
• $f(4)=f(3)+f(2)=3+2=5$

因此选 B. 5。