Exponential sum using recursion in Python

Question

I found here: exponential sum using recursion.python

Exactly the same problem with the same conditions to implement.

A brief description: We have started studying recursion and got some questions to solve using only recursion without any loop.

So we are asked to write a function calculating the exponential sum.

So here are my tries:

def exp_n_x(n, x):

    if n <= 0:
        return 1
    return (x/n)*exp_n_x(n-1, x)

It actually only calculates the n'th one, without summing up the others to i=0.

I tried to make the function sum every exponential element so:

def exp_n_x(n, x):

    if n <= 0:
        return 1
    sum = (x/n)*exp_n_x(n-1, x)
    n = n - 1
    return sum + (x/n)*exp_n_x(n-1, x)

But it doesn't help me... Thanks.

are you sure you're running python 3? because python 2 would zero most of the terms because of integer division. What's your parameters like? — Jean-François Fabre
– Jean-François Fabre ♦, Commented Nov 29, 2018 at 18:43
Yes... Python interpreter is 3.7. n is an integer and x is float. rhubarbdog - yes. — HelpMe
– HelpMe, Commented Nov 29, 2018 at 18:45
Are you trying to achieve that function in the link at the top of your post sigma x to the i over i factorial — phil
– phil, Commented Nov 29, 2018 at 18:45
Please see my answer below. The value of n is effectively i in the equation of your link, which decreases from its initial value to 0 (opposite but equivalent to the summation of i from 0 to n). — Dylon
– Dylon, Commented Nov 29, 2018 at 21:55

Dylon · Accepted Answer · 2018-11-29 18:52:33Z

2

You are pretty close to a solution in the first function, but you are missing two critical things: you need to raise x to the power of n and divide it by n! (n-factorial). The factorial function is the product of all integers from 1 to n, with a special case that 0! is 1. Also, you are creating a product when you need a sum. Putting these together you have:

def factorial(n):
    if n < 2:
        return 1
    return n * factorial(n - 1)


def exp_n_x(n, x):
    if n < 1:
        return 1
    return x ** n / factorial(n) + exp_n_x(n - 1, x)

answered Nov 29, 2018 at 18:52

Dylon

1,76017 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

HelpMe Over a year ago

Why can't we do all the recursion in one function that both multiplying ans summing? Thanks!

Dylon Over a year ago

There's nothing stopping you from doing that, it would just be more complicated.

Blckknght · Accepted Answer · 2018-11-30 18:03:20Z

0

I think your problem is that the sum you're computing has terms that can be computed from the previous terms, but not (as far as I can see) from the previous sums. So you may need to have two separate recursive parts to your code. One computes the values of the next term based on the previous term, and one that adds the new term to the previous sum.

def term(n, x):
    if n <= 0:
        return 1
    return x / n * term(n-1, x)

def exp_sum(n, x):
    if n <= 0:
        return 1
    return exp_sum(n-1, x) + term(n, x)

This is hideously inefficient, since the terms for the smaller n values get computed over and over. But that's probably OK for learning about recursion (I expect you'll learn about ways to avoid this issue with memoziation or dynamic programming eventually).

Note that you can combine the two functions into one, as long as you don't mind changing the function signature and returning two values at once (in a tuple) from the recursion. You could add a non-recursive helper function to make the user-facing function work as expected:

def exp_sum_recursive(n, x):            # this function returns term, sum tuples
    if n <= 0:
        return 1, 1
    term, sum = exp_sum_recursive(n-1, x)
    term *= x / n                       # each new term is based off of the previous term
    return term, sum + term             # the new sum adds the new term to the old sum

def exp_sum(n, x):                      # this is a non-recursive helper function
    return exp_sum_recursive(n, x)[1]   # it only returns the sum from the recursive version

edited Nov 30, 2018 at 18:03

answered Nov 29, 2018 at 18:53

Blckknght

106k11 gold badges135 silver badges188 bronze badges

2 Comments

HelpMe Over a year ago

Why can't we do all the recursion in one function that both multiplying ans summing? Thank you!

Blckknght Over a year ago

Hmm, you probably could combine them if you don't mind changing the function signature. It would need to return both the running sum, and the last term. To match the desired signature, you'd need a (non-recursive) helper function. I'll add that to my answer.

cdlane · Accepted Answer · 2018-11-30 19:18:00Z

0

Since you've achieved recursion with exp_n_x() why throw an inefficient recursive factorial() in the mix when Python already provides us with one:

from math import factorial

def exp_n_x(n, x):
    return 1 if n < 1 else x ** n / factorial(n) + exp_n_x(n - 1, x)

answered Nov 30, 2018 at 19:18

cdlane

42.2k5 gold badges37 silver badges87 bronze badges

Collectives™ on Stack Overflow

Exponential sum using recursion in Python

3 Answers 3

2 Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related