# Is this recurrence relation valid?

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?

• The way the recurrence works is that in order to evaluate $f(k)$, if $k = 2n$ is even then you use the third line, and if $k = 2n+1$ is odd then you use the fourth line. – Qiaochu Yuan Aug 7 '16 at 2:37

$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.