The recurrence relation is defined as follows:
$$f(0) = 1$$ $$ f(1) = 1$$ $$ f(2n) = f(n)$$ $$ f(2n+1) = f(n) + f(n-1)$$
I am supposed to calculate $f(10)$, however I have a hard time wrapping my head around this; I can't see any way the relation terminates to the base case.
For instance letting $n = 2$, a simple case supposedly, We get the relation: $$ f(4) = f(2), f(5) = f(2) + 1 $$ If we roll it even further the recurrence just gets larger and larger, not smaller. I don't see a way to solve this using a classical divide and conquer approach.
I am wondering if this is some sort of mistake made by the person that created this question? If not, what am I overlooking?