Recursion function - Python

Question

This is the problem:

Write a recursive function f that generates the sequence 0, 1, 0.5, 0.75, 0.625, 0.6875, 0.65625, 0.671875, 0.6640625, 0.66796875. The first two terms are 0 and 1, every other term is the average of the two previous.

>>> f(0)
0
>>> f(1)
1
>>> f(2)
0.5
>>> [(i,f(i)) for i in range(10)]
[(0, 0), (1, 1), (2, 0.5), (3, 0.75), (4, 0.625), (5, 0.6875), (6, 0.65625), (7, 0.671875), (8, 0.6640625), (9, 0.66796875)]

This is my code so far, I can't seem to figure it out. Any help/suggestions would be appreciated.

def f(n):
  if n==0:
    return 0
  if n==1:
    return 1
  else:
    return f(n-2)//f(n-1)

Answer 1

Recursion à la auxiliary function

You can define this using a simple auxiliary procedure and a couple state variables – the following f implementation evolves a linear iterative process

def f (n):
  def aux (n, a, b):
    if n == 0:
      return a
    else:
      return aux (n - 1, b, 0.5 * (a + b))
  return aux(n, 0, 1)

print([f(x) for x in range(10)])
# [0, 1, 0.5, 0.75, 0.625, 0.6875, 0.65625, 0.671875, 0.6640625, 0.66796875]

---

Going generic

Or you can genericize the entire process in what I'll call fibx

from functools import reduce

def fibx (op, seed, n):
  [x,*xs] = seed
  if n == 0:
    return x
  else:
    return fibx(op, xs + [reduce(op, xs, x)], n - 1)

Now we could implement (eg) fib using fibx

from operator import add

def fib (n):
  return fibx (add, [0,1], n)

print([fib(x) for x in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Or we can implement your f using fibx and a custom operator

def f (n):
  return fibx (lambda a,b: 0.5 * (a + b), [0, 1], n)

print([f(x) for x in range(10)])
# [0, 1, 0.5, 0.75, 0.625, 0.6875, 0.65625, 0.671875, 0.6640625, 0.66796875]

---

Wasted computations

Some answers here are recursing with (eg) 0.5 * (f(n-1) + f(n-2)) which duplicates heaps of work. n values around 40 take astronomically longer (minutes compared to milliseconds) to compute than the methods I've described here.

Look at the tree recursion fib(5) in this example: see how fib(3) and fib(2) are repeated several times? This is owed to a naïve implementation of the fib program. In this particular case, we can easily avoid this duplicated work using the auxiliary looping function (as demonstrated in my answer) or using memoisation (described in another answer)

Tree recursion like this results in O(n²), whereas linear iterative recursion in my answer is O(n)

---

Generating a sequence for n

Another answer provided by @MadPhysicist generates a sequence for a single n input value – ie, f(9) will generate a list of the first 10 values. However, the implementation is simultaneously complex and naïve and wastes heaps of computations due to the same f(n-1), andf(n-2)` calls.

A tiny variation on our initial approach can generate the same sequence in a fraction of the time – f(40) using my code will take a fraction of a second whereas these bad tree recursion answers would take upwards of 2 minutes

(Changes in bold)

def f (n):
  def aux (n, acc, a, b):
    if n == 0:
      return acc + [a]
    else:
      return aux (n - 1, acc + [a], b, 0.5 * (a + b))
  return aux(n, [], 0, 1)

print(f(9))
# [0, 1, 0.5, 0.75, 0.625, 0.6875, 0.65625, 0.671875, 0.6640625, 0.66796875]

Answer 2

Another simple solution might look like this:

a=0.0
b=1.0
count = 0
def f(newavg, second, count):

    avg = (second+newavg)/2
    print avg

    count=count+1
    if count<8:
        newavg = avg
        f(second, avg, count)
f(a, b, count)

Granted this code just outputs to the monitor...if you want the output into a list just add the code in the recursion.

Also be careful to properly indent where required.

Answer 3

If you want a function that generates your sequence in a single call, without having to call the function for each element of the list, you can store the values you compute as you unwind the stack:

def f(n, _sequence=None):
    if _sequence is None:
        _sequence = [0] * (n + 1)
    if n == 0 or n == 1:
        val = n
    else:
        f(n - 1, _sequence)
        f(n - 2, _sequence)
        val = 0.5 * (_sequence[n - 1] + _sequence[n - 2])
    _sequence[n] = val
    return _sequence

This has the advantage of not requiring multiple recursions over the same values as you would end up doing with [f(n) for n in range(...)] if f returned a single value.

You can use a more global form of memoization as suggested by @RightLeg to record the knowledge between multiple calls.

Unlike the other solutions, this function will actually generate the complete sequence as it goes. E.g., your original example would be:

>>> f(9)
[0, 1, 0.5, 0.75, 0.625, 0.6875, 0.65625, 0.671875, 0.6640625, 0.66796875]

Answer 4

So you have U0 = 0, U1 = 1, and Un = (U(n-1) + U(n-2)) / 2 for n > 1.

You just have to literally translate this as a function:

def f(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return (f(n-1) + f(n-2)) / 2

Now for generating the sequence of the Ui from 0 to n:

def generate_sequence(n):
    return [f(i) for i in range(n)]

This could (and really should) be optimized with memoization. Basically, you just have to store the previously computed results in a dictionary (while you could directly use a list instead in this case).

results = dict()
def memoized_f(n):
    if n in results:
        return results[n]
    else:
        results[n] = f(n)
        return results[n]

This way, f(n) will be computed only once for each n.

As a bonus, when memoized_f(n) is called, the results dictionary holds the values of f(i) from 0 to at least n.

Answer 5

The recursive case is wrong:

return f(n-2)//f(n-1) # not the formula for the average of two numbers

The average of two numbers a and b is (a+b)/2. So you can define your function as:

def f(n):
    if n==0:
        return 0
    if n==1:
        return 1
    else:
        return (f(n-1)+f(n-2))/2

Or we can make it Python version-independent like:

def f(n):
    if n==0:
        return 0
    if n==1:
        return 1
    else:
        return 0.5*(f(n-1)+f(n-2))

You can then generate the sequence with list comprehension like:

>>> [f(i) for i in range(10)]
[0, 1, 0.5, 0.75, 0.625, 0.6875, 0.65625, 0.671875, 0.6640625, 0.66796875]

or by using a map:

>>> list(map(f,range(10)))
[0, 1, 0.5, 0.75, 0.625, 0.6875, 0.65625, 0.671875, 0.6640625, 0.66796875]