What is implicit recursion?

Question

What is implicit recursion? How does this differ from explicit recursion?

Answer 1

I have not often used this term. A Google search showed use in a lambda calculus book. This book states the following:

• An equation that claims to be a definition should not include the thing defined on the right. (I agree with it.)

• If an equation like

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

  appears, we will call it "implicit recursion" and say that it is illegal. (I doubt it a bit.)

I do not know why this term is considered useful; for me it's just another terminology. It is important to distinguish the true mathematical definition from the recursion equation, which must be solved. Not every recursion equation has a useful or interesting solution; for example, although the factor function is the solution for the FAC above, the only useful solution for

 x = x + 1 

is “bottom”, which may mean “wrong” or “undefined” or “discrepancy”.

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

When it comes to practical programming languages, this whole discussion is extremely academic. Programming languages ​​are fully tuned to support "implicit recursion", although explicit fixed-point compilers are also surprisingly useful .

Answer 2

I heard the terms Explicit and Implicit recursion for comparing recursive function definitions (explicit), for example:

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

With functions that use explicitly recursive functions like fold and map , (implicit), for example:

 sum xs = foldr (+) 0 xs