FunctionRacerProblemsRace

Halve or Split

EasyRecursionPython, JavaScript, TypeScript, Java, C++

A sequence t is defined for every non-negative index by these rules: t(0) = 0, t(1) = 1, for an even index t(2k) = t(k), and for an odd index t(2k + 1) = t(k) + t(k + 1). Return t(n).

The rules are recursive and following them directly is the point; a loop with a table works as well but takes more thought.

For example, t(5) = t(2) + t(3), where t(2) = t(1) = 1 and t(3) = t(1) + t(2) = 2, so t(5) = 3.

Example 1

n 5
returns 3

5 is odd with k = 2, so t(5) = t(2) + t(3) = 1 + 2 = 3.

Example 2

n 0
returns 0

t(0) is given directly as 0.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Recursion problems