Python recursion doesn't yield desired result

Question

I am trying to find the length of the string with out using the inbuilt len() function. Here's my python code:

increment = -1
def lenRecur(aStr):
    '''
    aStr: a string

    returns: int, the length of aStr
    '''
    global increment

    if aStr == '':
        return increment
    else:
        increment += 1
        return lenRecur (aStr[increment:])
print lenRecur ("abcdefq")

The result I am expecting is 7 but what I got was 4.What I realized was when the increment became 2, the value pass to the lenRecur (aStr[increment:]) was "defq". Which means aStr[2:] is evaluated as "defq" instead of "cdefq".

Why this is happening?

That is because you are doing 2 deductions in each step - First, increasing the value of increment and second, slicing the string on each iteration , keep control over any one and you will be done . — ZdaR, Jan 28 '15 at 10:04
As a side note I'm not a big fan of using globals inside a recursive function. — Sylvain Leroux, Jan 28 '15 at 10:08

score 3 · Answer 1 · answered Jan 28 '15 at 10:07

Your function should not depend on external variables.

def lenRecur(aStr):
    '''
    aStr: a string

    returns: int, the length of aStr
    '''
    if aStr == '':
        return 0
    else:
        return 1 + lenRecur(aStr[1:])


print lenRecur("abcdefq")

score 0 · Answer 2 · edited May 23 '17 at 11:57

As an other option, you could write this:

def lenRecur(aStr):
    return _lenRecur(aStr, 0)

def _lenRecur(aStr, acc):
    if not aStr:
        return acc

    return _lenRecur(aStr[1:], acc+1)

A noticed by @gboffi in his answer, it is commonly accepted in Python to use a default argument instead of using of an helper function:

def lenRecur(aStr, acc = 0):
    if not aStr:
        return acc

    return lenRecur(aStr[1:], acc+1)

The choice of one form or the other will depend how much you want/don't want to allow the called to set the initial accumulator value to something else than 0.

Anyway, the interesting point here is in using an accumulator as the second parameter. That way, you have proper tail recursion. Unfortunately, this is not properly optimized by Python. But this is a good habit as many other languages have such optimization. And this will be a required skill if you switch someday to functional programing language.

score 0 · Answer 3 · answered Jan 28 '15 at 10:29

0

A common idiom is to use a default argument:

>>> def l(s, c=0): return l(s[1:], c+1) if s else c

This kind of solution works with anything that can be sliced

>>> l('pip')
3
>>> l([1,2,3])
3
>>> l('')
0
>>> l([])
0
>>>

answered Jan 28 '15 at 10:29

gboffi

22,939
8
54
85

Python recursion doesn't yield desired result

3 Answers3