Last installment, we found we could write a factorial function with a function call in the recursive branch, but not a recursive call. This ‘nearly recursive’ style allows us to write factorial without using its name. We just *assume* we have a free-variable delegate to some function that performs the rest of the computation. At initialization time, set the delegate to refer to the function itself. Thus, replace recursion with a call through a free variable. Just another level of indirection, as the cliché goes.

We need exactly this technique when we need recursive functions where explicit recursion isn’t allowed, as in lambda expressions.

Well, how about getting rid of the recursive definitions? Why bother with all these gymnastics just to write supposedly elegant functions, when loops and tests will do, eh? Two reasons: many algorithms are very hard to write correctly without recursion, and two, much more importantly, because we **can**. Part of my job is to explore all the implications of our technology. If something is possible, I have to try it. And I get to have fun doing it, too.

There is endless discussion of recursion versus iteration. It’s always possible to transform recursion into tail-recursion, and most compilers automatically convert tail-recursion into iteration. But many algorithms are very difficult, even for experts, to write straight-up correctly in iterative form. Quicksort and merge sort are famous, and binary search is infamous. Just about any graph or tree algorithm is best written recursively. Finally, when coding, it’s usually best to transcribe recursive specifications as recursive programs, notwithstanding notorious counterexamples like Fibonacci.

So, let’s take it as given that programmers need recursion as an intellectual tool for writing correct programs faster, secure in the knowledge that there are many ways to attack problems that might arise. That’s the real justification for studying toy problems like factorial: they represent much larger challenges, but in a small form that promotes full understanding of the principles at play.

Last time, we indulged in imaginary extensions to VB, allowing us to curry a function applied to itself, to create a closure containing the delegate to call in place of the recursion. The closure part is very easy to model in non-imaginary VB. Consider

** **Delegate** **Function** df(**ByVal** n **As** **Long**) **As** **Long

That’s the type needed for a factorial function. Next, define one as something that creates a new instance of **Class cf**, short for **closure of f**, which loads a private instance variable (closure environments are externally invisible) then calls a pseudo-lambda of type **df** in that closure. This is our somewhat clumsy transcription of the imaginary Dim fact = f(f), which presupposes currying. Don’t worry, it will get less clumsy as we go along.

** **

** **Function** fact1(**ByVal** n **As** **Long**) **As** **Long

** **Return** (**New** cf1).lambdaF(n)**

** **End** **Function

** **

** **Class** cf1**

** **REM This is a free variable in lambdaF:

** **Private** adf **As** df**

** **REM The following is our simulation of self-application:

** **Sub** **New**()**

** **Me**.adf = **AddressOf** **Me**.lambdaF**

** **End** **Sub

** **REM Here is the non-recursive version, that calls itself

** **REM indirectly through the delegate stored in the closure:

** **Public** **Function** lambdaF(**ByVal** n **As** **Long**) **As** **Long

** **If** n = 0 **Then** : **Return** 1**

** **Else** : **Return** n * adf(n - 1)**

** **End** **If

** **End** **Function

** **End** **Class

This is pretty easy, and accounts for the idea of a closure, modeling it as an instance of a class that contains bindings for free variables. Of course, the closure here is statically special-cased, but a generalized technique is all-but-obvious:

** **Function** fact2(**ByVal** n **As** **Long**) **As** **Long

** **Return** (**New** cf2).****lambdaF(n)**

** **End** **Function

** **

** **Class** cf2**

** **Private** env **As** **New** Dictionary(**Of** **String**, df)**

** **Sub** **New**()**

** **Me**.env(**"adf"**)**** = **AddressOf** **Me**.lambdaF**

** **End** **Sub

** **Public** **Function** lambdaF(**ByVal** n **As** **Long**) **As** **Long

** **If** n = 0 **Then** : **Return** 1**

** **Else** : **Return** n * **Me**.env.Item(**"adf"**)****(n - 1)**

** **End** **If

** **End** **Function

** **End** **Class

or, even more generally

** **Class** dfFreeVars**

** **Protected **env **As** **New** Dictionary(**Of** **String**, df)**

** **End** **Class

** **Class** cf2**

** **Inherits** dfFreeVars**

** ...**

Let’s say the point is made: we can easily implement environments for free variables, thus we have that part of closures licked. Henceforth, since environments will be very small, let’s not bother with the full generality of dictionary types in superclasses, remembering that we can easily do this when we need the generality.

We still have the vexing problem that we don’t really have lambda, self-application, and currying, just a rather lame simulation for them. Lambda will take us far into high orbit in another installment, but currying and self-application we can fake up right now:

** **Function** fact3(**ByVal** n **As** **Long**) **As** **Long

** **Dim** acf3 = **New** cf3 **REM Make a var so we can self-apply:

** **REM chained calls represent currying

** **Return** acf3.lambdaH(**AddressOf** acf3.lambdaH)(n)**

** **End** **Function

** **Class** cf3**

** **REM This type represents functions that take (delegate)

** **REM functions as their first argument and return (delegate)

** **REM functions of a different type:

** **Delegate** **Function** dh(**ByVal** adh **As** dh) **As** df**

** **REM Here's the free variable we've closed over:

** **Private** adh **As** dh**

** **Private** **Function** lambdaF(**ByVal** n **As** **Long**) **As** **Long

** **If** n = 0 **Then** : **Return** 1**

** **REM Self-application and currying, call-on-call:

** **Else** : **Return** n * adh(adh)(n - 1)**

** **End** **If

** **End** **Function

** **REM The factorial MUST self apply to inflate the closure:

** **Public** **Function** lambdaH(**ByVal** adh **As** dh) **As** df**

** **Me**.adh = adh**

** **REM Ooh, look, mom: a way to break access control!

** **Return** **AddressOf** lambdaF**

** **End** **Function

** **End** **Class

See what’s happened? **Fact3** gins up a closure by self-application of the one public method of **cf3**. That closure returns a (delegate to a) function of a numerical argument, so it’s curried. **Fact3** then just calls the curried function. There is just a tiny bit of excess generality here, as **lambdaH** could be applied to any function of (delegate) type **dh**; it just so happens we always self-apply it, both when **cf3** is instantiated in **fact3**, and internally to **lambdaF**, where external self-application is mimicked internally.

There is much, much more to do over the next few installments. First of all, we don’t really have a full lambda yet. Sure, we can make functions that don’t refer to their names internally, but we still refer to them externally. Second, this is all specialized to factorial, so far: we need to make this recursion-elimination technique work for any recursive function whatever. Third, we’ve just replaced call recursion with type recursion. The stuff above only works because type **dh** can refer to itself. That’s so self-application will work in a static-typing ambience. We could get rid of that through late-binding, and I might show something like that: I haven’t decided yet. But there is another technique.