What is implicit recursion?

Question

What is implicit recursion? How is it different from explicit recursion?

Answer 1

I've not seen the term used often. A Google search revealed a usage in a book on the lambda calculus. That book is arguing as follows:

1. An equation that claims to be a definition should not include the thing defined on the right-hand side. (I agree with this.)

2. If such an equation, like

   FAC = \n. if n = 0 then 1 else n * FAC (n-1),
   

   does show up, we'll call it "implicit recursion" and say it's illegal. (I'm a bit dubious about this.)

I don't know why this term is considered useful; to me it's just another piece of terminology. The important thing is to distinguish a true mathematical definition from a recursion equation, which has to be solved. Not every recursion equation has a useful or interesting solution; for example, although the factorial function is a solution for FAC above, the only useful solution for

x = x + 1

is "bottom", which may stand for "wrong" or "undefined" or "divergence".

I think the line in the textbook is trying to distinguish between "implicit recursion" (which I would call a recursion equation or a recursive equation) and a mathematical definition that uses an explicit fixed-point operator like the Y combinator.

When it comes to practical programming languages, all this discussion is extremely academic. Programming languages are totally set up to support "implicit recursion", although explicit fixed-point combinators are also surprisingly useful.

Answer 2

I've heard the terms explicit and implicit recursion to contrast recursive function definitions (explicit), eg:

sum (x:xs) = x + sum xs
sum [] = 0

With functions that use explicitly recursive functions like folds and map, (implicit), eg:

sum xs = foldr (+) 0 xs