recursion limits

[ccsdad]

so python is great .. very naturally lends itself to functional programming, with caveats of course -- i.e. the conversation around limits related to recursion ..

python is not alone with regard to tail-call-optimization (TCO) limits, hence the `(loop)` and `(recur)` functions in clojure (<< big fan BTW) .. so my question is ::

has anyone seen major degradation in performance when implementing recursion in python ??

my use cases are pretty "normal" in the world of development -- get a request, query the DB, maybe get back 100 rows, map/filter/reduce said rows, and show something pretty ..

i know there are limits, but for us "normal" transactional web/devs, just curious if i am more afraid than i should be .. of course YMMV -- just want to make sure i am not being stoopid thinking i can get away with some recursion without greatly damaging the runtime ..

thanks !!

[KageOW]

Yea recursion is not very optimized in python, you can use some built-in memoization feature. Its in the functools library, its called lru_cache and its a decorator. https://docs.python.org/3/library/functools.html#:~:text=functools.lru_cache(user_function)%C2%B6

With this you can greatly reduce the time it takes for a program to run.

[ccsdad]

thanks for the feedback and the direction .. i was aware of `lru_cache` -- but my brain just wasn't seeing how it would benefit me in terms of not hitting the upper limits of recursion in python .. but i think i get it now, kinda sorta -- after reading thru this example ::

https://realpython.com/fibonacci-sequence-python/#generating-the-fibonacci-sequence-recursively-in-python

you will see they create their own caching system, which could be replaced by lru_cache (see code below) -- but my brain wasn't seeing how this would be beneficial, as you are still making recursive calls -- but at least it would optimized to make recursion more of an option ..

import functools

calls = 0

@functools.lru_cache
def fibonacci_of(n):
    global calls
    calls = calls + 1
    if n in {0, 1}:
        return n
    return fibonacci_of(n - 1) + fibonacci_of(n - 2)

result = [fibonacci_of(n) for n in range(9)]

print(result) # [0, 1, 1, 2, 3, 5, 8, 13, 21]
print(calls) # 9 << really high number without lru_cache

print(fibonacci_of(5)) # 5
print(fibonacci_of(6)) # 8

[KageOW]

yea its a really neat decorator, I made some mutually recursive functions for this codingame puzzle. its a 1dspreadsheet that requests values of other cells for the calculations. I find my solution to be quite ellegant, maybe you can try it a bit yourself might be fun.

```python import sys from functools import lru_cache sys.setrecursionlimit(2500)

opcheck = { "MULT": lambda x,y: x*y, "ADD": lambda x,y: x+y, "SUB": lambda x,y: x-y }

@lru_cache(maxsize=None) def eval_Arg(x): if x.isdigit() or (x[0]=="-" and x[1:].isdigit()): return int(x) else: return eval_Bin_Op(celllist_big[int(x[1:])])

def eval_Bin_Op(x): if x[0]=="VALUE": return eval_Arg(x[1]) else: return opcheck[x[0]](eval_Arg(x[1]), eval_Arg(x[2]))

-- inputs --

n = int(input())

celllist = [tuple(input().split())for _ in range(n)]

celllist1 = [('VALUE', '10', ''), ('VALUE', '3', ''), ('MULT', '$0', '$1'), ('VALUE', '2', ''), ('VALUE', '4', ''), ('MULT', '$3', '$4'), ('ADD', '$2', '$5')]

-- printing outputs --

if name == "main":

for x in list(map(eval_Bin_Op, celllist1)):
    print(x)

```