0

I'm trying to translate a complicated excel spreadsheet to python, here's a simple example of what the excel spreadsheet looks like:

r       a               b          c            d
1       2%             a(r)+1   b(r)*2+a(r)   100
2to100  d(r-1)*.0001   a(r)+1   b(r)*2+a(r)   d(r-1)*c(r)

Here's what I wrote:

def a(r):
  if r==1:
    return 0.02
  else:
    return d(r-1)*0.0001
def b(r):
  return a(r)+1
def c(r):
  return b(r)*2+a(r)
def d(r):
  if r==1:
    return 100
  else:
    return d(r-1)*c(r)

I understand this is a naive example and I don't need a, b and c and can combine everything into one recursive function, but the real spreadsheet is more complicated and it takes a lot of effort to combine them.

Now my question is with efficiency. if I write the recursive functions separately, function (a) is being called 3 times each step and will quickly get out of hand. Is there a way to write the function so (a) is only called once each step?


calling d(100) is equivalent of calling function (a) 3^100=5.1*10^47 times and is impossible to finish.


Thanks to Tuqay in the comment, adding the following code solved the problem and speed up d(100) to less than a second

from functools import lru_cache
@lru_cache(maxsize = 128)
def a(r):
  if r==1:
    return 0.02
  else:
    return d(r-1)*0.0001
def b(r):
  return a(r)+1
def c(r):
  return b(r)*2+a(r)
def d(r):
  if r==1:
    return 100
  else:
    return d(r-1)*c(r)/3
4
  • 1
    Have you tried the naive recursion? Computers are pretty fast... (and premature optimisation is the root of all evil) Commented Sep 29, 2021 at 21:44
  • 4
    Take a look at at cache from functools. It will cache the results and will not recalculate Commented Sep 29, 2021 at 21:48
  • 1
    The trivial answer is you can store the result of the call to a() in a local variable and reuse it without calling the function over and over, as long as the value of r doesn't change (you'd have to know it doesn't) - but is agonising over optimisations that win milliseconds at best worth your time at this juncture? Very often, readable code saves you (or another coder) more time in the future, than it does the user of highly optimised code. Commented Sep 29, 2021 at 21:49
  • To be frank, recursive functions get "out of hand" only because we let them .. Time is one thing .. If your definition of "out of hand" is the amount of time it takes the program to complete it's task, that's subjective. So if you mean "out of hand" by the amount of time it takes, then that just may always be the case with complicated recursion. Else you're talking "overhead" which, so long as you are trash collecting when needs be, and avoiding unnecessary runs using handling -- There is nothing wrong with running function a) as many times as it needs to run. Commented Sep 29, 2021 at 21:50

1 Answer 1

1

Thanks to Tuqay in the comment, adding the following code solved the problem and speed up d(100) to less than a second

from functools import lru_cache
@lru_cache(maxsize = 128)
def a(r):
  if r==1:
    return 0.02
  else:
    return d(r-1)*0.0001
def b(r):
  return a(r)+1
def c(r):
  return b(r)*2+a(r)
def d(r):
  if r==1:
    return 100
  else:
    return d(r-1)*c(r)/3
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.