Python :: Iteration vs Recursion on string manipulation

Question

In the examples below, both functions have roughly the same number of procedures.

def lenIter(aStr):
    count = 0
    for c in aStr:
        count += 1
    return count

or

def lenRecur(aStr):
    if aStr == '':
        return 0
    return 1 + lenRecur(aStr[1:])

Picking between the two techniques is a matter of style or is there a most efficient method here?

I realise that this is just a simple example task to allow you to discuss the difference between iteration & recursion, but in real code you should use `len()`. All the built-in Python container types store their length as an attribute so calling `len()` on them is _very_ efficient. — PM 2Ring, May 28 '16 at 08:53
FWIW, there's some good info about optimization in Python in [this answer](http://stackoverflow.com/a/7166368/4014959), especially the advice to use builtins and module functions that run at C speed rather than coding your own version that runs at Python speed. — PM 2Ring, May 28 '16 at 10:03
@PM 2Ring thanks...I am aware of built-in types and how they should by all means be used. I was just trying to deepen the understanding on the nature of code that leads to those functions — 8-Bit Borges, May 29 '16 at 03:29

score 2 · Accepted Answer · edited May 23 '17 at 12:24

2

Python does not perform tail call optimization, so the recursive solution can hit a stack overflow on long strings. The iterative method does not have this flaw.

That said, len(str) is faster than both methods.

edited May 23 '17 at 12:24

Community

1
1

answered May 28 '16 at 05:18

John Kugelman

349,597
67
533
578

score 2 · Answer 2 · answered May 28 '16 at 05:20

This is not correct: 'functions have roughly the same number of procedures'. You probably mean that: 'these procedures require the same number of operations', or, more formally 'they have the same computational time complexity'.
While both have the same computational time complexity, the one using recursion requires additional CPU instructions to execute code for creating new instances of procedures during recursion, and to switch contexts. And to clean up after returning from every recursion. While these operations do not increase the theoretical computational complexity, in most real life implementations of operating systems they will put significant load.
Also the resursive method will have higher space complexity, as each new instance of recursively-called procedure needs new storage for its data.

Nice answer, but you should also mention that Python has a recursion limit, so the recursive version will fail for long strings. — PM 2Ring, May 28 '16 at 08:40

Mazdak · Answer 3 · 2016-05-28T05:24:53.073

Surely the first approach is more optimized, as python doesn't have to do a lot of function call and string slicing, which each of these operations are contain some other operations that cost much for python interpreter, and may be cause a lot of problems in future and in dealing with log strings.

As a more pythonic way you better to use len() function in order to get the length of a string.

You can also use code object to see the required stack sized for each function:

>>> lenRecur.__code__.co_stacksize
4
>>> lenIter.__code__.co_stacksize
3

Python :: Iteration vs Recursion on string manipulation

3 Answers3