Actually what does that look like with a stack within one function call? Is it always possible to write recursive functions with a stack (in order to avoid and the function call overhead (which includes a locals() dict on a stack anyway for every function call))
"Why is a function/method call in python expensive?" https://stackoverflow.com/questions/22893139/why-is-a-function-method-call-in-python-expensive "Python max recursion, question about sys.setrecursionlimit()" https://stackoverflow.com/questions/7081448/python-max-recursion-question-about-sys-setrecursionlimit > sys.setrecursionlimit(limit)¶ > Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python. > > The highest possible limit is platform-dependent. A user may need to set the limit higher when she has a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash https://docs.python.org/3/library/sys.html#sys.setrecursionlimit Python doesn't have Tail Call Optimization, so there's no *performance* benefit to the recursive form with CPython: >From https://en.wikipedia.org/wiki/Tail_call : > Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is no longer needed, and can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail-call elimination or tail-call optimization. >From https://github.com/kachayev/fn.py#trampolines-decorator : ```rst Trampolines decorator --------------------- ``fn.recur.tco`` is a workaround for dealing with TCO without heavy stack utilization. Let's start from simple example of recursive factorial calculation: .. code-block:: python def fact(n): if n == 0: return 1 return n * fact(n-1) This variant works, but it's really ugly. Why? It will utilize memory too heavy cause of recursive storing all previous values to calculate final result. If you will execute this function with big ``n`` (more than ``sys.getrecursionlimit()``) CPython will fail with .. code-block:: python >>> import sys >>> fact(sys.getrecursionlimit() * 2) ... many many lines of stacktrace ... RuntimeError: maximum recursion depth exceeded Which is good, cause it prevents you from terrible mistakes in your code. How can we optimize this solution? Answer is simple, lets transform function to use tail call: .. code-block:: python def fact(n, acc=1): if n == 0: return acc return fact(n-1, acc*n) Why this variant is better? Cause you don't need to remember previous values to calculate final result. More about `tail call optimization < http://en.wikipedia.org/wiki/Tail_call>`_ on Wikipedia. But... Python interpreter will execute this function the same way as previous one, so you won't win anything. ``fn.recur.tco`` gives you mechanism to write "optimized a bit" tail call recursion (using "trampoline" approach): .. code-block:: python from fn import recur @recur.tco def fact(n, acc=1): if n == 0: return False, acc return True, (n-1, acc*n) ``@recur.tco`` is a decorator that execute your function in ``while`` loop and check output: - ``(False, result)`` means that we finished - ``(True, args, kwargs)`` means that we need to call function again with other arguments - ``(func, args, kwargs)`` to switch function to be executed inside while call ``` But to your actual question, what does %timeit say when you benchmark match-case vs if-else? From https://jakevdp.github.io/PythonDataScienceHandbook/01.07-timing-and-profiling.html : ```quote Here we'll discuss the following IPython magic commands: - %time: Time the execution of a single statement - %timeit: Time repeated execution of a single statement for more accuracy - %prun: Run code with the profiler - %lprun: Run code with the line-by-line profiler - %memit: Measure the memory use of a single statement - %mprun: Run code with the line-by-line memory profiler The last four commands are not bundled with IPython–you'll need to get the line_profiler and memory_profiler extensions, which we will discuss in the following sections. ``` That being said, recursive syntax is good to learn especially for languages with Tail Call Optimization: https://en.wikipedia.org/wiki/Recursion_(computer_science) > Most computer programming languages support recursion by allowing a function to call itself from within its own code. Some functional programming languages (for instance, Clojure)[4] do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in computability theory that these recursive-only languages are Turing complete; this means that they are as powerful (they can be used to solve the same problems) as imperative languages based on control structures such as while and for. > > Repeatedly calling a function from within itself may cause the call stack to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less efficient, and, for large problems, it is fundamental to use optimization techniques such as tail call optimization.[citation needed] On Tue, Nov 16, 2021, 20:59 kirby urner <kirby.ur...@gmail.com> wrote: > > So are we encouraged to use match-case in recursion instead of if-else? > > It's more readable this way maybe: > > cubocta310.py: > > def cubocta(n): > """ > https://oeis.org/A005902 > """ > match n: > case 0: return 1 > case _: return (10*n*n + 2) + cubocta(n - 1) > > print([cubocta(i) for i in range(10)]) > > (py310) Kirbys-MacBook-Pro:School_of_Tomorrow mac$ python cubocta310.py > [1, 13, 55, 147, 309, 561, 923, 1415, 2057, 2869] > > https://flic.kr/p/2mKh2nd > (image version) > > Kirby > > _______________________________________________ > Edu-sig mailing list -- edu-sig@python.org > To unsubscribe send an email to edu-sig-le...@python.org > https://mail.python.org/mailman3/lists/edu-sig.python.org/ > Member address: wes.tur...@gmail.com >
_______________________________________________ Edu-sig mailing list -- edu-sig@python.org To unsubscribe send an email to edu-sig-le...@python.org https://mail.python.org/mailman3/lists/edu-sig.python.org/ Member address: arch...@mail-archive.com
