CODEWITHSUNDEEP
pythonrecursionlinked-list
Art
Art

Reputation: 275

How to store values in a recursive function?

Suppose you have the following recursive function. Assume the node argument is the head:

def to_string(node):
    a_str = ""

    if node.next != None:
        a_str += str(node.val)
        to_string(node.next)
    else:
        return a_str

I would like to record the value of all of the nodes. The code is able to obtain the values, since it is calling itself with the next node, to_string(node.next), but it is not able to store the values and return the correct string since a_str is re-initialized upon every call. Is there a in-function solution to this, or will I have to rely on global variables?

Upvotes: 6

Views: 10191

Answers (1)

Mad Physicist
Mad Physicist

Reputation: 114320

You aren't returning a value in one case. Written properly, your function should look like this:

def to_string(node):
    a_str = str(node.val)
    if node.next != None:
        a_str += to_string(node.next)
    return a_str

Strings are immutable, so you don't need to initialize to anything other than the current node.

As to answer your question as to how to store things in a recursive function pythonically: you can use nested functions. A nested function can use a non-local variable in your main function scope to emulate a global without leaking anything out:

def to_string(node):
    def actual_recursive(node):
        nonlocal a_str
        a_str += str(node.val)
        if node.next != None:
            actual_recursive(node.next)
    a_str = ''
    actual_recursive(node)
    return a_str

The nonlocal keyword is a lot like global, but it lets you modify the value of the immediately surrounding function's scope.

Upvotes: 5

Related Questions