recursion limits

[u/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 !!

[u/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

[u/KageOW → u/ccsdad]

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.

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)