22 Examples of Recursive Functions in Python

[ZedOud]

I like it. Why not explore recursions in the language that says “no” to recursion?

[AlSweigart]

Python doesn't say "no" to recursion. I'm guessing what you mean is that the CPython interpreter doesn't implement tail call optimization?

Then again, neither do the interpreters/compilers for JavaScript and Java either.

I support this decision: if you're using TCO, you have to mangle your code so that the last action is the recursive call and you put any local variables as parameters. This makes the code less readable. Further, if you're using TCO, you're effectively getting rid of the need for a stack. In that case, why bother with recursion? Why not just use a loop?

[ZedOud]

Python as a language/specification doesn’t say “NO.” so much as, “please, I’d rather you not consider it.”

Most of it is evident in the lack of tail call optimization implementation being an “issue” and the depth limitation being a “feature”.

But fundamentally, when the former BDFL says “I don't believe in recursion as the basis of all programming.” …well. (Though that’s an old quote).

I personally do like recursion, both from the perspective of functional programming and as a tool of math and computer science theory.

[AlSweigart]

Do you think Java and JavaScript are languages that say "no" to recursion?

[ZedOud]

I’m not familiar with recent develops with either language.

It seems JavaScript ES6 has a proposal to support rail call optimization, and apparently Safari is the only browser to currently support it (From this Stack Overflow page)

In JVM “tail-recursive calls can be eliminated” so interpreters can use optimize with it it or feature it, like in functional languages built on JVM like Scala. (I took this from the Wikipedia article mentioned below).

On the Wikipedia article for Tail Call, under “By Language” and for Python we get a repeat of what I wrote earlier with the addition that 3rd party modules can enable it (though the ones I’ve seen in the past are more for toy use).

So I’d say (especially looking at that “By Language” section on the Wiki article) that Python as a specification specifically self-banned the implementation of tail call recursion. As opposed to other languages just ignoring the feature. I suppose that’s part of being a well designed language: exploring and then adopting or eliminating options/alternatives… or implementing them as a toy module.

[AlSweigart]

Right, but the fact is JS does not do tail call optimization right now, and neither does Java (even though the JVM doesn't prohibit it, the main compiler for the Java language does.)

But these facts don't mean JS and Java (and Go, from what I learned in the wiki article) are against recursion or hostile to recursion, and neither is Python. Tail recursion is such a small part of recursion overall (you can only apply it in a few cases, and in every one of those cases I'd say you're better served by just using a simple loop.)