Recursive algorithm for calculating arithmetic mean

Question

I am making an algorithm that has to calculate the average values of a list, but with what I did does not present the correct result. The sum works, but when it comes to dividing, no.

def media(l,s=0):
    if len(l) == 0:
        return s
    else:
        return media(l[1:],s+l[0]) / len(l)

media()

Answer 1

^{Just remembering that recursion is not the best way to calculate the average (and below we will see the reasons). Anyway, here are some alternatives.}

---

In your code, every recursive call you create a sub-list containing the second element on (l[1:]), and you divide the result by the size of these sub-lists (i.e., if the original list has 3 elements, l[1:] will have 2 elements and you will add these 2 elements and divide the result by 2, then add with the first element and divide everything by 3, so it doesn’t work). The right would be to divide only at the end, when you already have the total sum of all the elements.

Therefore, an alternative is to control the index of the element in which we are to know whether or not to divide:

def media_recursiva(valores, i = 0, n = None):
    if n is None: # se n não foi passado, usar o tamanho da lista
        n = len(valores)

    # último elemento, retorna o próprio
    if i == n - 1:
        return valores[i] 

    # dividir por n toda a soma computada 
    if i == 0:
        return (valores[i] + media_recursiva(valores, i + 1, n)) / n

    # computar soma (sem dividir)
    return valores[i] + media_recursiva(valores, i + 1, n)

print(media_recursiva([3, 6, 7])) # 5.333333333333333

Notice that only when i for zero, I divide by n (which in this case is the list size, that is, the number of numbers). In other cases, I only add the values. Another advantage with respect to its function is that it does not need to create a sub-list because the values of i already control the index of the element I want to pick up, so I can pass the same list in all recursive calls.

---

Another alternative (as inefficient as the previous one) is to add and divide, and multiply back, with each recursive call.

def media_recursiva2(valores, n = None):
    if n is None:
        n = len(valores)

    if n == 1:
        return valores[0]

    return (valores[n - 1] + ((n - 1) * media_recursiva2(valores, n - 1))) / n

print(media_recursiva2([3, 6, 7])) # 5.333333333333333

Basically, we always divide the value by n (which in turn decreases its value with each recursive call), and multiplied back to get the original value.

The basic idea is that to calculate the mean of N values, I first calculate the mean of N - 1 values (which will be the sum of these N - 1 values, divided by N - 1). Then, in order for the sum to correspond to the N-th value plus the sum of the N - 1 remaining, I multiply this average by N - 1 before adding to the N-th value, so that at the end I have the sum of the N values. Then just divide it all by N.

It’s basically the algorithm you were trying to do (always divide with each recursive call), but with a multiplication to "nullify" the effects of the previous divisions. A very "ugly" and inefficient turn, by the way.

---

Finally, I would like to make it clear that using a recursive algorithm to calculate average is not the best solution. Even if it is an exercise to study recursion, it is still questionable, since it is a bad use case for this resource (see more about this here and here).

Also, depending on the size of the list, the amount of recursive calls can cause a pile overflow. And the list it doesn’t even have to be that big.

If you want to calculate the average in a simpler and more direct way, do it:

def media(valores):
    return sum(valores) / len(valores)

---

^{The above recursive algorithms have been removed from here and from here.}

Answer 2

You want the average of a list passed to a function recursively, so do this:

l=[3,6,7]

def media(l):


    if len(l) == 1:

        return l[0]
    else:
        return  l[0] + media(l[1:])

media(l)
print("A média da sua lista é: ", (media(l)/len(l)))

See working on Ideone

Note that your stop condition has been improved for when the list contains 1 element: len(l)==1.

The average of the list l[3,6,7] is 5.33 and not 8 as you quoted in the comments.