I think I’ve posted this here before but the best short explanation of recursion I’ve ever heard was from my programming languages professor 35 years ago when we were testing out algorithms in a toy Lisp we had to write at the start of the course. All non-infinite recursive algorithms should have a “base case and a smaller caller”, meaning there needs to be a terminal state and the algorithm should narrow its scope on each recursive call. I still use that to this day when I happen to need to write a recursive algorithm.
This sounds a lot like what Coq enforces programmatically to avoid any programs that don't terminate from compiling (since there's no other looping construct in the language). If I remember correctly, languages like this are called "primitive recursive", and in some ways I think it's a bit unfortunate that we've converged on Turing complete languages as the only paradigm used for most real world things; I feel like there's untapped potential for making primitive recursive languages more ergonomic (like some sort of syntax for "simple" loops that can be syntactic sugar for having to manually define a recursive function).
"Primitive recursive" applies to functions, not languages, and -from a practical, programmer's point of view- it refers to recursive functions that can be "unrolled" in an iterative loop (or just a sequence of repeating steps).
Non-primitive recursive functions are functions that are recursive but can't be "unrolled", like the Ackermann function (which was specifically created as a demonstration that there exist such functions).
Recursion doesn't have to be complicated. It's the syntax of most programming languages that makes it complicated. For example in Prolog, a clause is recursive if it has a literal in the body that has the same symbol and number of arguments as in the head literal. This is easy to show with an example:
That's a recursive predicate. The first clause is not recursive- it's the terminating condition. The second clause is recursive. The second occurrence of "head(X,Y)" is the recursive call.
The only reason you can't do that in Python is because the syntax doesn't make it easy. In Prolog a clause is a set of literals and a program is a set of clauses so recursion is very simple and natural to express as a re-occurring literal like I explain above.
You're right about me misremembering the terminology here, but I feel like in your focus on the details you've kind of glossed over the larger point that I was trying to make, which is that having a language where you _can't_ define something non-terminating (like you can in Turing complete languages) is still enough to do quite a lot, and I think it's a bit of a shame that there aren't that many mainstream options for this.
Many apologies, I didn't mean to be pedantic, only informative.
I did get the point you are making, but I wasn't sure what to say about it so I didn't say anything. Let me give it a go now. The problem with Turing completeness is that you don't know whether you'll need it until you do. There are non-Turing complete languages around of course, like e.g. HTML (far as I can tell). You can do quite a lot with HTML but, for example, you can't really define business logic.
In logic programming (Prolog is a logic programming language) there have been some efforts to eliminate the non-termination of recursion in Prolog while retaining the good parts of the logic-based and declarative paradigm. The result is languages like Datalog and Answer Set Programing (unfortunately abbreviated as ASP; long before ASP.Net though), which certainly have their place and certainly let you define complex behaviour, including recursive procedures. On the other hand, both languages don't let you use lists. You know, lists: [1,2,3]. Lists are recursive data structures and without the possibility of unbounded recursion- you can only have fixed-length lists. People in the ASP community know how to simulate lists by essentially breaking them up in single elements and having some code that looks for the next element, but that's a clunky, hacky, and incomplete notation that just goes to show what a mess one makes when one tries to make something better by making it worse. I'm afraid that's a pattern that applies to much more than logic programming and trying to make programming languages safe by making it impossible to write non-terminating code, will only do the same thing.
Non-termination is by no means something you get only with recursion of course. I like to say this story at length but I'll spare you the details: I was working in a C# shop and one bug that brought the company servers down (that was before the cloud) was caused by a foreach loop with a faulty condition. There was a talk about all that "upstairs". It was put to the suits that it is impossible to guarantee that an iterative loop will terminate, and the decision was made to... use recursion instead. In C#. Obviously that was completely ignored by everyone. That goes to show... something. But mainly that you can jolly well make a mess with unbounded iteration, as with unbounded recursion.
So in general I think what you say sounds good on paper but it won't work in practice. It's a bit like asking why can't we have a campfire that won't burn your marshamallows. Well because fire burns and that's the whole point. The undecidability of Turing-complete languages is not an academic curiosity. It's a direct result of the power of computers. You can remove the undecidability bu then you've taken away the power.
This is fine as a beginner rule of thumb but it shouldn't be regarded as a universal truth about recursion. Its also possible for a simple evaluation without recursion to happen at infinity rather than at zero. In practice this usually means picking a large value of the input as a cut off point to apply an approximation or return a standard value instead.
For example, take an implementation of exp(x). The exponential function is defined as the sum to infinity of (x^n)/n!. This could be implemented recursively as exp(x,n) = 1+(x/n)exp(x,n+1). The challenge is to figure out the value (or criteria) for what value of n to cut this infinite evaluation short. Well, once n is larger than x all future terms will be multiplied by a factor less than 1. So pick some proportionality constant k such that if x is k times smaller than n (that is, x * k < n) then the remainder is presumed negligible and the function returns 1.
Another really nice example I know involves finding the resistance across a simple but infinitely repeating circuit. At very large n, there are so many resistors in the way that the contribution of the remaining circuit connected in parallel is basically nothing. So pick whatever value of net resistance R_N for an arbitrary cut off point N, then recursively find the net resistance in the circuit up to point N-1 connected in parallel with everything remaining in the circuit after point N.
There are other cases I can think of where the base case is actually the function converging (or becoming linear) for large rather than small inputs. And still other cases I know of where the function has more than one input argument, and thus it might make sense to increase the size in one input to reduce it in another etc.
>> All non-infinite recursive algorithms should have a “base case and a smaller caller”, meaning there needs to be a terminal state and the algorithm should narrow its scope on each recursive call.
Oh, well, I don't like that, sorry. Recursion is a syntactic property but what you explain here is an algorithmic one. Unbounded recursion, non-terminating recursion and left-recursion are still recursion. My intuition is that you should teach termination and recursion as different concepts and help students understand that they are not the same. So that they learn to avoid non-terminating recursion that is.
Btw I think what you describe is called a Knuth-Bendix ordering.
The simplest example is with factorial. The "base case" is when we hit 0 or 1, we want to return 1. By identifying and defining this case first you ensure that your program's execution will be bounded (which is normally what we want):
def factorial(n):
if n == 0 or n == 1:
return 1
# recursive case(s)
This is an incomplete program, the next part is to identify each of the recursive calls. In this case there's just one, and it's achieved by reducing `n` by 1 and multiplying the result of the call by the current `n`:
def factorial(n):
if n == 0 or n == 1:
return 1
return n * factorial(n - 1)
And if you're using a non-braindead interpreter/compiler you'd make this more efficient by using tail-calls (these get optimized away by reasonable language implementations, the main Python implementation is not reasonable):
def factorial(n, accum=1):
if n == 0 or n == 1:
return accum
return factorial(n - 1, accum * n)
For more complex cases, consider a binary tree or node in an abstract syntax tree (AST). Assuming an ordered binary tree (left node is less than current node, right is greater than the current node) and a search over the tree (this is also easy to do without recursion at all but for the illustration):
Assume the node is something like this:
@dataclass
class Node:
item: int = 0
left: Node = None
right: Node = None
def search(node, value):
# 1st base case: the value was not found
if node is None:
return False
# 2nd base case: the value was found
if node.item == value:
return True
Again, at this point the program is not complete but we've identified the two base cases. The next step is to figure out the recursive step(s). In this case there are two recursive steps but only one will be taken (if we aren't at the base cases yet): go left or go right.
def search(node, value):
if node is None:
return False
if node.item == value:
return True
if node.item < value:
return search(node.left, value)
if node.item > value:
# technically this test will always be true if we reach this point
# so the right search can be made unconditional. I put this here
# to be more explicit, remove the test to be more efficient.
return search(node.right, value)
If your data structure or problem has a recursive structure, you can use this approach.
