I write plenty of recursive functions in my (real world) job. Sometimes they're not even tail recursive (gasp) when I'm working with small data.
Anyway, I am all for allowing tail recursion in a language, if it is supported properly by the compiler/interpreter. Just forbid general recursion, if you don't intend to support it properly.
The way this works in Smalltalk is that primitives (e.g. equality on numbers) return an object which is either `true` or `false`. These object each have their own implementations of methods such as `ifTrue:` and `ifFalse:` which accept code blocks. `true ifTrue: [ … ]` always runs the given code block, while `false ifTrue: [ … ]` never runs it. At a machine-code level the comparison primitives are most likely implemented with native conditions and branches, and the VM bytecode does include conditional branches for the sake of optimization, but in terms of the high-level language it's all based on the equivalent of C++ virtual method calls or C function pointers. Smalltalk has no syntax for conditions, or any syntactic equivalent of the C switch statement. (A dictionary or array of code blocks is typically used instead.)
Technically you can do without the comparison primitives if you encode your data in certain ways, e.g. using Peano numbers (and switching to Lambda Calculus):
false = λt. λf. f
true = λt. λf. t
zero = λf. λx. x
succ = λn. λf. λx. f (n f x)
one = succ zero
two = succ one
…
isZero = λn. n (λx. false) true
import Foundation
typealias T = ()
typealias ChurchNum = ((T) -> T, T) -> T
func zero() -> ChurchNum {
return { (f, x) in x }
}
func succ(_ g : @escaping ChurchNum) -> ChurchNum {
return { (f, x) in f(g(f, x)) }
}
func add(_ g : @escaping ChurchNum, _ h : @escaping ChurchNum) -> ChurchNum {
return { (f, x) in h(f, g(f, x)) }
}
func numeral(_ n : Int) -> ChurchNum {
var z : ChurchNum = zero()
for _ in 0 ..< n {
z = succ(z)
}
return z
}
func realise(_ g : ChurchNum) -> Int {
var n : Int = 0
func f(_ x : T) -> T {
n += 1
return x
}
g(f, ())
return n
}
let x : ChurchNum = add(numeral(100000), numeral(100000))
print("x = \(realise(x))") {-# LANGUAGE RankNTypes #-}
module Main where
type ChurchNum = forall x. (x -> x) -> x -> x
zero :: ChurchNum
zero = \f x -> x
succ' :: ChurchNum -> ChurchNum
succ' g = \f x -> f (g f x)
add :: ChurchNum -> ChurchNum -> ChurchNum
add g h = \f x -> h f (g f x)
numeral :: Int -> ChurchNum
numeral 0 = zero
numeral n = succ' (numeral (n - 1))
realize :: ChurchNum -> Int
realize g = g (+1) 0
main :: IO ()
main = do
let x = add (numeral 100000) (numeral 100000)
putStrLn ("x = " <> show (realize x))
I also wonder, what about recursion in Haskell? Is it limited by the stack size as in more conventional languages?
Probably Haskell just allocates a very large stack size, and does it otherwise in the standard way. Otherwise it should be able to do much more than 20M.
There is some talk about it here: https://gitlab.haskell.org/ghc/ghc/-/issues/8189
In any case, the point was not that we should all use recursion on Church-encoded Peano numbers for computation, since that is obviously very inefficient, but rather that tail recursion in particular—which does not result in excessive stack use, when implemented sanely—is a more general construct than iteration. It can be used to implement iteration, of course, but also other control flow patterns like state machines and coroutines which would otherwise require additional language support. The only major obstacle is poor language implementations, mostly for imperative languages (including Java), which insist on storing contextual data on the stack which is provably no longer needed by the program. Kotlin is a bit better but still hampered by the limitations of the JVM, so some kinds of tail calls (not direct recursion) still use stack space. EMCAScript 6 specifies guaranteed tail-call elimination, which should benefit Typescript, but Safari appears to be the only major environment which gets it right so far[0].
[0] https://kangax.github.io/compat-table/es6/#test-proper_tail_...
The sum is just function composition, so not likely. In terms of using the sum, it depends on the function being applied and whether the evaluation model is lazy or strict. (And your stack size, of course.) The isZero function I gave above, for example, only needs to process the outermost "succ" or "zero" and the rest is ignored, which is perfect for lazy evaluation:
isZero zero
= (λn. n (λx. false) true) (λf. λx. x) -- def. of isZero and zero
= (λf. λx. x) (λx. false) true -- β-reduce n
= (λx. x) true -- β-reduce f
= true -- β-reduce x
isZero (succ N) -- for any N
= (λn. n (λx. false) true) ((λn. λf. λx. f (n f x)) N) -- def. of isZero and succ
= (λn. λf. λx. f (n f x)) N (λx. false) true -- β-reduce n
= (λf. λx. f (N f x)) (λx. false) true -- β-reduce n
= (λx. false) (N (λx. false) true) -- β-reduce f
= false -- β-reduce x
If you want to compute, then things like stack overflow matter very much. See my example in Swift.
Is recursion helpful? Of course! Is tail recursion more useful than just the normal control structures like iteration that are already at your disposal? I doubt it, but as I said before, I wouldn't mind having properly implemented tail recursion at my disposal.
Everything in a modern language is optional, but people are not rushing to program in a assembly.
I am not arguing against recursion. I am saying, do it right. Otherwise it is useless.