Given recursive expression, find algorithm with space complexity O(1)

Question

I have been given the task to write an algorithm given this simple expression:

f (0) = 0, f (1) = 1, f (2n) = f (n), f (2n + 1) = f (n) + f (n + 1).

The restrictions are: Time Complexity O(logn), Space Complexity O(1). I wrote this basic recursion function:

int func (int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n % 2 == 0) {
        return func(n / 2);
    } else {
        return func(n / 2) + func((n / 2) + 1);
    }
}

There is probably something smarter using an iterative algorithm because I need O(1) space complexity (I think my code is not O(1) space because of the recursive calls).

Observe that with an even argument you can divide it by two until it's odd, and only then call the function. Apply same logic to the odd argument. — GSerg, Apr 24 '18 at 19:53
Possible duplicate of [Efficiently generating Stern's Diatomic Sequence](https://stackoverflow.com/questions/41229066/efficiently-generating-sterns-diatomic-sequence) — Paul Hankin, Apr 24 '18 at 20:34
I answered, but then searched for dupes and found one. Note that the accepted answer there is poor, but https://stackoverflow.com/a/44557597/1400793 provides a solution that's a little simpler than mine. — Paul Hankin, Apr 24 '18 at 20:35

Paul Hankin · Accepted Answer · 2018-04-24T20:36:57.060

This sequence is Stern's diatomic sequence, and the function you've been given is called fusc(n).

One way to compute it in O(log n) time and O(1) space complexity is to find the n'th value in the Calkin-Wilf tree. That value's numerator will be fusc(n). You can read some background on the wikipedia page: https://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree

Here's some code that checks the naive fusc implementation with the fast version. It's in Python, but it would be trivial to convert to C++.

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


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


for i in xrange(100):
    assert fusc(i) == fast_fusc(i)

You can see that in fast_fusc, top iterates over the bits of n, so the code performs O(log n) arithmetic operations. There's only 4 variables used (n, a, b, top) so it uses O(1) space.

Given recursive expression, find algorithm with space complexity O(1)

1 Answers1