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?
$f(10)=f(5)=f(2)+f(1)=f(1)+f(1)=1+1=2.$
The recurrence is well-defined because the relations defining $f(n)$ always replace the argument n of the function with smaller and smaller values of n. Eventually these values must reach 0 or 1, at which point the base cases take care of the situation.