The fusc function is defined recursively as follows:

    1. fusc(0) = 0
    2. fusc(1) = 1
    3. fusc(2 * n) = fusc(n)
    4. fusc(2 * n + 1) = fusc(n) + fusc(n + 1)
    

The 4 rules above are sufficient to determine the value of `fusc` for any non-negative input `n`. For example, let's say you want to compute `fusc(10)`. 

1. `fusc(10) = fusc(5)`, by rule 3.
2. `fusc(5) = fusc(2) + fusc(3)`, by rule 4.
3. `fusc(2) = fusc(1)`, by rule 3.
4. `fusc(1) = 1`, by rule 2.
5. `fusc(3) = fusc(1) + fusc(2)` by rule 4.
6. `fusc(1)` and `fusc(2)` have already been computed are both equal to `1`.

Putting these results together `fusc(10) = fusc(5) = fusc(2) + fusc(3) = 1 + 2 = 3`

Your job is to produce the code for the `fusc` function. In this kata, your function will be tested with small values of `n`, so you should not need to be concerned about stack overflow or timeouts. 

Hint: Use recursion.

When done, move on to [Part 2](http://www.codewars.com/kata/the-fusc-function-part-2).

Source: codewars | Difficulty: EASY

Starter code: def fusc(n):
	

Solutions:
def fusc(n):
	assert type(n) == int and n >= 0
	if n < 2:
		return n
	if n % 2 == 0:
		return fusc(n // 2)
	else:
		return fusc(n // 2) + fusc(n // 2 + 1)


def fusc(n):
	f = [0, 1]
	for i in range(1, n + 1):
		f.append(f[i])
		f.append(f[i] + f[i + 1])
	return f[n]


def memoize(func):
	cache = {}

	def newfunc(*args):
		if args not in cache:
			cache[args] = func(*args)
		return cache[args]
	return newfunc

@memoize
def fusc(n):
	assert type(n) == int and n >= 0
	if n < 2:
		return n
	return fusc(n / 2) + fusc(n / 2 + 1) if n % 2 else fusc(n / 2)


def fusc(n):
	return n if n < 2 else fusc(n // 2) + (n % 2 and fusc(n // 2 + 1))


def fusc(n):
	(a, b) = (1, 0)
	while n > 0:
		if n & 1:
			b = a + b
		else:
			a = a + b
		n >>= 1
	return b


def fusc(n):
	return n if n <= 1 else fusc(n / 2) + (fusc(n / 2 + 1) if n % 2 == 1 else 0)


def fusc(n):
	if n < 2:
		return n
	if n % 2:
		m = (n - 1) // 2
		return fusc(m) + fusc(m + 1)
	return fusc(n / 2)


def fusc(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n % 2 == 0:
		return int(fusc(n / 2))
	if n % 2 != 0:
		return int(fusc((n - 1) / 2)) + int(fusc((n - 1) / 2 + 1))