Recursion and while loops: pros and cons

General Usage
,
1

This recursive function:

function foo1(x)
    y = someoperations(y)
    if somecondition(y)
        return y
    else
        return foo1(y)
    end
end

does essentially the same as with the loop:

function foo2(x)
    y = someoperations(y)
    while !somecondition(y)
        y = someoperations(y)
    end
    return y
end

But Julia does not implement it in the same way. There is a function-call overhead in the recursive version - or at least there was such an overhead in earlier versions, according to this old thread. On the other hand, if somecondition is never met, the loop will run forever, whereas after a given number of recursive calls Julia will stop and throw an error, so it feels safer.

What are other advantages and drawbacks of either approach? (If there is anything to add to what was already mentioned in the linked thread above.)

2

What you are looking for is tail call elimination (also called as tail call optimization or tail recursion optimization). There have been a number of threads on the subject here, e.g. this one. According to this discussion, “Julia doesn’t have tco currently, and is fairly unlikely to add it.” That being said, a macro is being considered on Github.

1 Like
3

This doesn’t answer your pros and cons question, but you can avoid an infinite loop by adding a variable that you increment with each iteration and check that it hasn’t exceeded some limit.

1 Like
4

I mark this as solution because, although I asked it as “pros and cons” of recursion vs. while-loop, my reason for asking about that is exactly what you are describing; just that I didn’t know it.

5

An additional resource that I found very to understand the relationship between what I asked and what @HanD answered (with Julia examples!):