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

Difficulty: introductory

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 fusc(n):
    assert type(n) == int and n >= 0
    if n < 2:
        return n
    if n & 1:
        return fusc((n - 1) // 2) + fusc(((n - 1) // 2) + 1)
    return fusc(n // 2)

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):
    assert type(n) == int and n >= 0
    if n <= 1:
        return n
    if n%2 == 0:
        return fusc(n/2)
    else:
        return fusc(n//2) + 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))