Using recursive function instead of loops

Question

I’m trying to build a scoring matrix using recursive,

    for i in range(1, len(str1))
        for j in range(1, len(str))
        #do something

my code:

def matrix_bulid(index_1, index_2):
    print(index_1, index_2)
    if index_1 == len(first_dna) and index_2 == len(second_dna):
        return
    elif index_2 == len(second_dna):
        return matrix_bulid(index_1 + 1, 1)
    else:
    #do something
            matrix_bulid(index_1, index_2 + 1)

but in really long strings , i get max depth error thing. does anyone has any idea how to do it?

Duplicate of http://stackoverflow.com/questions/6900241/python-function-composition-max-recursion-depth-error-scope ? — shantanoo, Nov 18 '13 at 19:28
Recursion isn't really a way to speed code up in all cases more just a method for solving problems that cannot be solved by iteration or are suited to recursion — ford prefect, Nov 18 '13 at 19:30
afaik pretty much all recursion can be done with loops ... recursion can sometimes make it more readable than loops (or not) — Joran Beasley, Nov 18 '13 at 19:31
@NPE: Python doesn't do tail call elimination, so that doesn't make any difference. — abarnert, Nov 18 '13 at 19:31
@JoranBeasley: All recursion can be done with a loop _and an explicit stack_. _Some_ recursion can be done with just a loop, like this case. But you're right, in some cases the recursive case is more readable (even when a stack isn't needed), and in those cases, as long as you've got bounded limits well below the stack depth, it's worth doing. — abarnert, Nov 18 '13 at 19:33
@NPE: He's trying to turn his already-working iterative code into recursive code. The fact that he can rewrite his recursive code to not use recursion is both obvious and useless. — abarnert, Nov 18 '13 at 19:34
@NPE: Well, the title is "Using recursive function instead of loops", and he showed us a working nested loop and a nearly-working recursive implementation of the same thing and asked how to make it work… — abarnert, Nov 18 '13 at 19:37
can somebody edit the question (maybe the OP), so that it's in English. — tmj, Nov 18 '13 at 19:47

score 2 · Answer 1 · edited May 07 '18 at 17:03

If your goal is to turn your nested for loop into a simple recursive function, you've done that successfully. There are some bugs (bad indentation, not returning anything in the second recursive case, …), but the basic structure is sound.

Unfortunately, recursive functions are bounded by the depth of the stack. Some languages have tail call elimination, which means tail-recursive functions aren't bounded. And your implementation is tail-recursive. But Python (intentionally) does not have that feature, so that doesn't matter; you can still only deal with strings up to sys.getrecursionlimit()+1 in length.

If your strings are bounded, but just a little too big for the default recursion limit (which is 1000 in CPython), you can use sys.setrecursionlimit to set it higher.

There are also tricks to simulate tail call elimination in Python, which I'll discuss below. But even with the best possible trick, your recursive code is still longer, less obvious, less Pythonic, and slower than your nested loop.

If you're doing this for a homework assignment, you're probably done. Unless you were given a choice of programming language, in which case you will need to choose a language with tail call elimination. If you're doing this for real code, you should stick with your original nested loops—the code is simpler, it will run faster, and there is no stack limit, without needing anything hacky or complicated.

The most efficient way to implement tail-call optimization in CPython is by modifying the bytecode of compiled functions, as here. But that's also the hackiest way, and it only works in a restricted set of circumstances.

The simplest way is to modify your function to return a function that returns a value, instead of a value, and then use a trampoline to chain the evaluations together (there are at least two blog posts that show this technique, here and here). But, while that's simplest to implement, it requires changes through your actual recursive functions, which make them more complicated and less readable.

The best tradeoff is probably to use a decorator that inserts a trampoline in the middle of each recursive step, so you don't need to delay function calls explicitly, as seen here. This can get a bit tricky if you have mutually-recursive functions, but it's rarely hard to figure out. And the implementation is pretty easy to understand. And it's not much slower than the bytecode hackery.

Using recursive function instead of loops

1 Answers1