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?

  • $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Aug 7 '16 at 2:37


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.

  • $\begingroup$ Thanks! I was thinking about it the wrong way, I understand it now. I think I'll be able to solve the rest of this problem set. $\endgroup$ – Liz Aug 7 '16 at 3:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.