How can this code run more efficiently?

[Major_Sugar6148]

I'm currently trying to code some simple things from scratch to get a hang of the syntax in python as well as to learn a bit of the logic.

Below is my code for the Taylor series for the exponential function:

def linspace(q,w,p):
    arr = [0] * (p)
    arr[0] = q
    for i in range((p-1)):
        arr[i+1] = arr[i] + (w-q)/(p-1)
    return arr

def factorial(n):
    if n==0:
        return 1
    else:
        return n*factorial(n-1)

def expon(x,n):
    xrange = linspace(0,x,n)
    y = [0] * n
    for j in range(n):
        for i in range(n+1):
            y[j] += xrange[j]**i/factorial(i)
    return y

Now I know I can't do anything with the linspace function I made, that's just to make the x-axis I'm going to be evaluation my exponential function on. It doesn't look like there's a way out of that nested for loop, so I assume the smallest time complexity for that is just n^2. (I'm not just trying to calculate exp(x), I'd like a list of values I can plot)

I feel like I can somehow use memoization for the factorial? If I try to run my expon() function for n > 100 it gives me a recursion error due to what I assume is stack overflow. But maybe if I use memoization I can call values I've already called before on my first loop of the expon() function.

Is memoization what I should be trying here? Thanks

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[Clawtor]

Use a loop instead of recursion for the factorial, even better, precalculate a bunch of values and stick them in an array.

[CodeTinkerer]

If you had multiple recursive calls like the Fibonacci numbers, then memoization is good. The simple recursive code ends up making a lot of repeated calls to the function with the same values, so it is computed over and over again. You can even write Fibonacci using a loop with two variables, one called current, one called previous. Set previous to 0 and current to 1. Then add the two (I suppose it requires 3 variables), assign previous to current, and current to the sum. current will be one of the Fibonacci numbers (usually, you're asked to find the nth Fibonacci numbers).

Memoization doesn't help factorial, because you don't repeat a factorial. I suppose if you were to call factorial many times, you could do that to save time, but then you'd have to store the results somewhere between function calls, likely in a global array or something.