[PYTHON] Transform Iterative methods to tail recursive and warn when recursive usage (team 904000m2)

[zabatakram]

In many languages, recursive operations are very costly (memory and cpu), mainly in python. Tail Recursive operations with less than 2 args can easily be converted to iterative methods and must raise an alert.

• Warning for every recursive operation (in python)
• Alert for tail recursive detected by the fact that the recursive call is the last operation of the method.

[LordPatate]

https://towardsdatascience.com/python-stack-frames-and-tail-call-optimization-4d0ea55b0542

[LordPatate]

https://pypi.org/project/tail-recursive/

[zabatakram]

\newpage

Optimized API: Avoid recursive calls and prefer iterative implementation for tail-recursion

Platform

OS	OS version	Langage
Web	{OS version}	Python3

Main caracteristics

ID	Title	Category	Sub-category
{id}	Avoid recursive calls	Environment	Optimized API
{id}	Prefer iterative implementation for tail-recursion	Environment	Optimized API

Severity / Remediation Cost

• Case 1: Iterative approach should be prefered to recursive in Python as the latter is highly memory consuming.

Severity	Remediation Cost
Major	High

• Case 2: Tail-recursive functions should be transformed into its iterative implementation

Severity	Remediation Cost
Major	Minor

Rule short description

In many languages, recursive operations are very costly (memory and cpu), mainly in python. The reason for this limit is (among other things) doing recursive calls takes a lot of memory and resources because each frame in the call stack must be persisted until the call is complete.

• Case 1: Iterative approach should be prefered to recursive in Python as the latter is highly memory consuming.
• Case 2: Tail-recursive functions should be transformed into its iterative implementation

Rule complete description

Text

In many languages, recursive operations are very costly (memory and cpu), mainly in python. The reason for this limit is (among other things) doing recursive calls takes a lot of memory and resources because each frame in the call stack must be persisted until the call is complete. Python has a default maximum recursion depth of 1000.

• Case 1 : Iterative approach should be prefered to recursive in Python as the latter is highly memory consuming. A warning shoud be returned when a recursive function is detected.

• Case 2: A function is tail-recursive if it ends by returning the value of the recursive call. Keeping the caller’s frame on stack is a waste of memory because there’s nothing left to do once the recursive call returns its value. Some compilers implement tail-call optimization, allowing unlimited recursion to occur without stack overflow. As Python is an interpreted language, an alternative is to refactor your code by your-self, or to ask a thirdparty library to do this for you.

|Sources:

• Deriving Iterative Algorithms from Tail-Recursive Functions - https://www.baeldung.com/cs/tail-vs-non-tail-recursion
• https://towardsdatascience.com/python-stack-frames-and-tail-call-optimization-4d0ea55b0542
• https://beapython.dev/2020/05/14/is-recursion-bad-in-python/
• Python tail-recursive library : https://pypi.org/project/tail-recursive/

HTML

<p>In many languages, recursive operations are very costly (memory and cpu), mainly in python. The reason for this limit is (among other things) doing recursive calls takes a lot of memory and resources because each frame in the call stack must be persisted until the call is complete. Python has a default maximum recursion depth of 1000.</p>
<ul>
<li><p>Case 1 : Iterative approach should be prefered to recursive in Python as the latter is highly memory consuming. A warning shoud be returned when a recursive function is detected.</p>
</li>
<li><p>Case 2: A function is tail-recursive if it ends by returning the value of the recursive call. Keeping the caller’s frame on stack is a waste of memory because there’s nothing left to do once the recursive call returns its value. Some compilers implement tail-call optimization, allowing unlimited recursion to occur without stack overflow. As Python is an interpreted language, an alternative is to refactor your code by your-self, or to ask a thirdparty library to do this for you.</p>
</li>
</ul>
<p>|Sources:</p>
<ul>
<li>Deriving Iterative Algorithms from Tail-Recursive Functions - <a href="https://www.baeldung.com/cs/tail-vs-non-tail-recursion">https://www.baeldung.com/cs/tail-vs-non-tail-recursion</a></li>
<li><a href="https://towardsdatascience.com/python-stack-frames-and-tail-call-optimization-4d0ea55b0542">https://towardsdatascience.com/python-stack-frames-and-tail-call-optimization-4d0ea55b0542</a></li>
<li><a href="https://beapython.dev/2020/05/14/is-recursion-bad-in-python/">https://beapython.dev/2020/05/14/is-recursion-bad-in-python/</a> </li>
<li>Python tail-recursive library : <a href="https://pypi.org/project/tail-recursive/">https://pypi.org/project/tail-recursive/</a></li>
</ul>

Implementation principle

• Foreach method check if the method calls itself
• If not call itself :
  • no alert and break
• Else :
  • warn of the use of a recursive method (case 1)
  • if recursive call is the last of the method :
    • raise an alert (case 2) and ask to refactor the code with the standard method described here https://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion

[LordPatate]

⚠️ This package tail_recursive shoud not be used as it comes with great costs: higher execution time, memory and CPU consumption

from tail_recursive import tail_recursive
@tail_recursive
def factorial(n):
    if n <= 1:
        return n
    # It is important that you return the return value of the `tail_call`
    # method for tail recursion to take effect!
    # Note tail calls work with dunder methods, such as __mul__ and __rmul__,
    # by default.
    return n * factorial.tail_call(n - 1)

# Implementation with tail recursion succeeds because the function is
# called sequentially under the hood.
factorial(900)

def factorial_without_tail_recursion(n):
    if n <= 1:
        return n
    return n * factorial_without_tail_recursion(n - 1)

factorial_without_tail_recursion(900)

vincent@vincent-HP-ProBook-450-G7:~/dev/poub$ vjoule --no-gpu python3 lords_patate.py s1 12.671363847795874

CGroup	CPU	RAM
Global	168.39J	11.06J
Process	104.98J	1.00J

vincent@vincent-HP-ProBook-450-G7:~/dev/poub$ vjoule --no-gpu python3 lords_patate.py s2 0.024966625031083822

CGroup	CPU	RAM
Global	0.51J	0.05J
Process	0.27J	0.01J

[LordPatate]

http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html