CODEWITHSUNDEEP
pythonfunctionrecursionsequence
Akule8
Akule8

Reputation: 37

recursive geometric sequence

I have a problem to get my code to work. I need to write a recursive function

geometric_recursive

The formula is enter image description here

My Problem is that i can't stop the loop. Also the function should have the same parameters as the iterative version

def geometric(n: int) -> float:
'''
Calculates a finite geometric series with q=0.5 as the base. 
'''
result = 0

for k in range(0, n+1):
    result += 0.5**k

my code is

    def geometric_recursive(k : int) -> float:
if k <= 0:
    return 1
else:
    return 0.5 ** geometric_recursive(k+1)

The goal is that the assert should be passed

assert geometric_recursive(2) == geometric(2)

I hope someone can help me

Upvotes: 0

Views: 593

Answers (3)

Serge Ballesta
Serge Ballesta

Reputation: 148890

First let us look at the formula on a mathematical point of view: SUM[0<=i<n](q**i) is (1 - q**n) / (1 - q). So for q=0.5 the expected resul is 2.

And the mathematics prove that we can compute it provided q < 1.

The common way will be to define a limit epsilon and stop the recursion when q**n < epsilon. We know that the number will be greater that 1, and that Python floating points have a precision close to 15 decimal digits (48 bits for the mantissa)

So we can write:

def g_recurs(q, term=1, tot=0):
    # print(q, term, tot)  # uncomment for intermediate results
    tot += term
    term *= q
    if term < 1E-16:       # stop recursion when q**n < 1E-16
        return tot
    else:
        return g_recurs(q, term, tot)

It gives as expected:

>>> g_recurs(0.5)
2.0

After your edit you only want to compute a specific number of terms, and q is fixed at 0.5. The formula would become:

 def g_recurs(n: int, term=1, tot=0) -> float:
    # print(q, term, tot)  # uncomment for intermediate results
    tot += term
    term *= 0.5
    if n == 0:
        return tot
    else:
        return g_recurs(n-1, term, tot)

It gives the expected value:

>>> g_recurs(2)
1.75

The above formule avoided the exponentiation because a multiplication is much simpler, but I now think that you were just looking for:

def geometric_recursive(n:int) -> float:
    if n == 0:
        return 1
    term = 0.5 ** n
    return term + geometric_recursive(n-1)

Which verifies too:

>>> geometric_recursive(2)
1.75

Upvotes: 1

saquintes
saquintes

Reputation: 1089

Recursion requires a base case. You have none (or none that will hit). The formula goes to infinity, but that's not practical. You need to figure out when you are close enough to an answer to stop. This can either be a number of iterations (Python has a max recursion depth that is one upper limit) or a level of precision.

Also, the function doesn't seem to represent the formula. The formula looks like the sum of q^k where as you have q ^ (q ^ (q ^ (q ^ ...))). There is no summation happening.

Upvotes: 0

HasanArcas
HasanArcas

Reputation: 37

Simply because you are giving as parametre k+1 everytime , so basically k will never be <= 0 , so that means that your function will call itself again and again

Upvotes: 0

Related Questions