Python recursive function that retain variable values

Question

I am brushing up a bit of good old algorithms, and doing it with python, since I use it more often nowadays.

I am facing an issue when running a recursive function; where the variable get reset every time that the recursive function call itself:

def recursive_me(mystring):
    chars = len(mystring)
    if chars is 0:
        print("Done")
    else:
        first = int(str[0])
        total = + first
        print(total)
        recursive_me(mystring[1:])

recursive_me("4567")

What I am doing here is to get a string made of digits; take the first, convert it to an int; and run recursively the function again, so I can take one digit at time from the string and sum all the values.

Ideally the output should show the total, while it add all the digits (4+5+6+7), although when the recursive function is called the first time, the function reset the total value.

Is common habit to use global variables when running operations with recursive functions or am I doing something wrong?

Answer 1

You can code as simply as this:

def recursive_me(mystring):
    if mystring: # recursive case
        return int(mystring[0]) + recursive_me(mystring[1:])
    else:        # base case
        return 0

or

def recursive_me(mystring, total = 0):
    if mystring: # recursive case
        return recursive_me(mystring[1:], total + int(mystring[0]))
    else:        # base case
        return total

although this won't help much in Python since it doesn't implement tail-call optimisation.

If you want to see the intermediate values, change the second version like so:

def recursive_me(mystring, total = 0):
    if mystring: # recursive case
        newtotal = total + int(mystring[0])
        print(newtotal)
        return recursive_me(mystring[1:], newtotal)
    else:        # base case
        return total

then

4
9
15
22
22 # this is the return value; previous output is from `print()`

Answer 2

as a foreword: a lot of answers received meaningful edits in the meantime I was writing this answer. Don't hold it against me.

I'm throwing my two cents in here just because there's a lot of over-complicated answers. This is a corrected copy-paste of the OP's effort.

def recursive_me(mystring, total=0):
    chars = len(mystring)
    if chars is 0:
        print("Done")
        return total
    else:
        first = int(mystring[0])
        total += first
        print(total)
        recursive_me(mystring[1:], total)

first what happens is that we check the base case, if there's no left chars in the string. If the string length is 0 we return the total calculated ammount.

Otherwise, we turn the first of the chars into an int, and add it to total. The first error you have is that you wrote str[0]. str is a python built in type and the produced error would be something like "str is not subscriptable".

This error means that the str can't be operated on by "[]" operator. The same would happen if you tried doing 1[0] because 1 is a integer. The "[]" operator can only operate on lists, tuples and strings (I might've forgot some built-in type).

The second error you had was with the addition part. You had written total = + first but the operator you are looking for is the += which in fact is just a shortened way to write a = a+b.

Additionally, your original question was concerning about "python" forgetting the value of "total". This is because you have to either pass that value forward, or write your recursive function in a way that "forces" it to, what's called, evaluate your next call to your function on the spot.

In my example I'm sending the next call of the function recursive_me, the current total value. In the example given by @uselpa; above he's making python evaluate the next call to the function by putting it after operator +:

return int(mystring[0]) + recursive_me(mystring[1:])

this then gets to be (for recursive_me("4567"))

return int(4)+recursive_me("567")
return int(4)+int(5)+recursive_me("67")
....
return int(4)+int(5)+int(6)+int(7)+0

because python needs to return a value here, but the expression keeps calling new functions and python can't return until it evaluates all of them to a final number (in this case at least).

Answer 3

The common practice is to save these variables as parameters, and pass them along the chain. It seems in your case, you would want to pass total as an additional parameter, and update it as needed.

There's also a neat functional way to do it in python

t=raw_input()
print reduce(lambda a, b: a+b, map(int,t))

This is recursive in nature.

Answer 4

Some pointers:

• Your default case should return an actual number (0 in your case) and not just print done.
• total = + first is setting total to first, not adding first to total. You would need total += first to do the latter.
• The trick with "retaining" the value of your current total is to "save" it in the recursive call-chain itself by passing it along with each call. You won't need a global variable or a default parameter to do this.

Here's a solution:

def recursive_me(mystring):
    if not mystring: # True if mystring is empty
        return 0
    return int(mystring[0]) + recursive_me(mystring[1:])

print(recursive_me("4567")) # 22

Answer 5

Here is a solution that uses the LEGB scope rule to avoid creating a new string instance on every recursive call

def sum_str(mystring):
    def recursive_me(pos):
        cur_char = int(mystring[pos])
        if pos:
            return cur_char + recursive_me(pos-1)
        else:
            return cur_char
    return recursive_me(len(mystring)-1)

s = '4567'
print('summing', s)
print(sum_str(s))

However, indexing can be avoided as well by iterating on the string

def sum_str(mystring):
    def recursive_me(itx):
        try:
            cur_char = int(next(itx))
            return cur_char + recursive_me(itx)
        except StopIteration:
            return 0

    return recursive_me(iter(mystring))

Obviously, both solutions produce

summing 4567
22