Avoiding stack overflow with functional programming

Question

I am trying to solve "the grid search" problem on hacker rank using functional programming. Please view the problem description on hackerrank. https://www.hackerrank.com/challenges/the-grid-search/problem

I want to use only recursion and functional programming primitives such as map, filter, etc. My current solution checks to see if it can find the pattern at the start of the array, if it can't, then I call recursively on the tail of the array. I came up with the following:

def checkLine(str1, str2):
    return str1 in str2

def checkGroup(group1, group2):
    return False not in list(map(lambda x: checkLine(x[0], x[1]), zip(group1, group2)))

def gridSearch(G, P):
    # Write your code here
    if len(G) < len(P):
        return "NO"
    if checkGroup(P, G):
        return "YES"
    else:
        return gridSearch(G[1:], P)

The issue is that I am running into stack overflow when both the array is very large. I know you can avoid stack overflow by using tail recursion but I'm not quite sure how to accomplish that here. Can anyone give an example of how solve this problem functionally but also avoid stack overflow?

You can increase the recursion limit, but doing so causes HackerRank to return a wrong answer. Are you sure your code is correct? — BrokenBenchmark, May 19 '22 at 00:08
" I know you can avoid stack overflow by using tail recursion " You cannot. CPython does not do tail-call optimization. Indeed, your grid-search function is already tail recursive. Fundamentally, you should just use iteration in Python when you want to use deep recursion. Python is not a functional programming langauge (although, it borrows from the paradigm, e.g. list comprehensions). — juanpa.arrivillaga, May 19 '22 at 00:10
See [Does Python optimize tail recursion?](https://stackoverflow.com/q/13591970/5987). — Mark Ransom, May 19 '22 at 00:11
@BrokenBenchmark It passed about 10 of the test cases but failed for the others that had very large input. Thanks for the replies. I see now that function I wrote is already tail recursive. — Sterling, May 19 '22 at 02:23

score 0 · Answer 1 · answered Jul 17 '22 at 12:59

I’m not really a Python programmer, so there might be more idiomatic ways of doing this, but in JavaScript I would use a technique known as trampolining:

def trampoline(original_function):
    def wrapped_function(*args):
        # Call the original function
        result = original_function(*args)
        # If a function is returned, call the function until
        # a non-function is returned, which is the final result
        while callable(result):
            result = result()
        return result
    return wrapped_function

# Factorial function example
def _fact(n, acc=1):
    if n == 0: return acc
    return lambda: _fact(n - 1, n * acc)
fact = trampoline(_fact)

def _gridSearch(G, P):
    # Write your code here
    if len(G) < len(P):
        return "NO"
    if checkGroup(P, G):
        return "YES"
    else:
        # note the lambda: here
        return lambda: _gridSearch(G[1:], P)
gridSearch = trampoline(_gridSearch)

I personally don’t like doing if callable(result) to check if the recursive function has outputted the final value, so another method could be to do something like this:

from dataclasses import dataclass

@dataclass
class Recurse:
    value: ...

@dataclass
class Return:
    value: ...

def trampoline(fn):
    def f(*args):
        x = fn(*args)
        while isinstance(x, Recurse):
            x = fn(*x.value)
        return x.value
    return f

# Factorial function example
def _fact(n, acc=1):
    if n == 0: return Return(acc)
    return Recurse((n - 1, n * acc))
fact = trampoline(_fact)

def _gridSearch(G, P):
    # Write your code here
    if len(G) < len(P):
        return Return("NO")
    if checkGroup(P, G):
        return Return("YES")
    else:
        return Recurse((G[1:], P))
gridSearch = trampoline(_gridSearch)

This way is more general than the other one as it works for recursive functions that return another function (but I can’t think of why you would need to do this).

Avoiding stack overflow with functional programming

1 Answers1