Recursion with Completion Handlers in Swift

We recently shipped Simple HDR, an app that controls the <a href="https://theta360.com/en/">Ricoh Theta</a> 360° camera. The app's key feature is the ability to capture a sequence of images with varying shutter speeds, which can then be used to create an <a href="https://en.wikipedia.org/wiki/High-dynamic-range_imaging" target="_blank">HDR</a> (high dynamic range) image. In the process of building this feature, we arrived at an interesting solution that relies on recursion.


As you may know, <a href="https://en.wikipedia.org/wiki/Recursion_(computer_science)" target="_blank">recursion</a> is the staple of iteration in <a href="https://en.wikipedia.org/wiki/Functional_programming" target="_blank">functional programming languages</a>, and can often be an elegant solution to problems otherwise addressed using messy looping constructs. “Elegant” here meaning, short, simple and, most importantly, easiest for your future self (who no longer has any recollection of the program logic) to figure out.


<a href="https://developer.apple.com/swift/" target="_blank">Swift</a>, being a functional language, is well suited to recursion. However, since we need to solving real world problems involving networking, persistence, etc., completion handlers are a fact of life. These add an interesting twist to the application of recursion since such closures can't return anything and values must be "returned" by passing them into the provided handler.


How can we do recursion without return values?


We'll get to that, but first, a refresher: the “Hello World!” of recursion is the calculation of <a href="https://en.wikipedia.org/wiki/Factorial" target="_blank">N!, or N factorial</a>, defined as N! = N*(N-1)*(N-2)*...1. For example, the factorial of 4 is 4*3*2*1, which gives us a result of 24.


One possible swift implementation is:

<pre class="lang:swift decode:true"> func factorial(N:Int) -&gt; Int {

    if N == 1 {

        return 1

    } else {

        return factorial((N-1)*N) // doing the multiplications here (in the returns)

    }

}</pre>

On each iteration, N is reduced by one and passed to the next call of factorial(). When N becomes 1, the function calls return and 1*…(N-1)*N is computed as execution returns to the scope of the initial call.


In recursion you have two options as to where the "work" (e.g. computation, networking, database access...) gets done. In the recursive implementation of factorial given above, the work(multiplications) are performed as execution returns back up the function call stack. The result accumulates in the return values and is available when control reaches the initial call to factorial().


You can also do your work on the way down(<a href="http://stackoverflow.com/questions/33923/what-is-tail-recursion" target="_blank">tail recursion</a>) so that it is completed when execution arrives at the recursive base case at the bottom of the call stack. In the case of factorial, this requires an additional argument where the result accumulates since we're not using the return values for this purpose.


A "work done on the way down"(tail-recursive) solution is:

<pre class="lang:swift decode:true ">func factorial(N:Int, oldTotal:Int) -&gt; Int {

    if N == 1 {

        return oldTotal // factorial has been computed

    } else {

        let newTotal = oldTotal * N // doing multiplications here (before the returns)

        return factorial(N-1, oldTotal:newTotal)

    }

}</pre>

The second argument complicates the function profile and the initial call must pass 1 (you could create a wrapper to keep your API pretty), but may be slightly more comprehensible for those new to recursion.


If performance is an issue, an additional benefit of tail-recursion is that it can be more easily optimized by a compiler.


Back to the camera: for the sake of simplicity let's say the picture taking function is the following:

<pre class="lang:swift decode:true">takePicture(shutterSpeed:Double, completionHandler:() -&gt; ())

</pre>

Taking the picture and storing it is actually a side-effect, not very functional, but that's the reality of the hardware.


The camera only accepts a request to take a new picture after the current picture taking process is complete, so kicking off all the requests in parallel and coordinating the results with  <a href="https://developer.apple.com/library/ios/documentation/Performance/Reference/GCD_libdispatch_Ref/" target="_blank">Grand Central Dispatch</a> (GCD) dispatch groups is not an option.


For a small, fixed number of pictures, the requests can simply be nested:

<pre class="lang:swift decode:true ">takePicture(shutterSpeeds[0], {

    takePicture(shutterSpeeds[1], {

        takePicture(shutterSpeeds[2], {

            print("We’ve taken 3 pictures.")

        }

    }

}</pre>

But for an arbitrary number of pictures, where that number might be large, the iterative solution is an ugly looping system with <a href="https://en.wikipedia.org/wiki/Semaphore_(programming)" target="_blank">semaphores</a> so that the loop waits until the handler for the last call to takePicture() executes. Note:since the handlers can come back at any time, on any thread, a simple flag won't do.


Something like:

<pre class="lang:swift decode:true ">for speed in shutterSpeeds {

    dispatch_semaphore_t wait_sema = dispatch_semaphore_create(0)

    takePicture(speed, {

        print("Done taking a picture.")

        dispatch_semaphore(wait_sema) // safe to call takPicture() again

    }

    while(dispatch_semaphore_wait(wait_sema), DISPATCH_TIME_NOW)) {

      // wait until the previous handler executes

      NSRunLoop.currentRunLoop.runUntilDate(NSDate.dateWithTimeIntervalSinceNow(0))

    }

}</pre>

I like GCD, but I try to avoid the additional complexity of semaphores whenever possible. Can we somehow get the simplicity of nesting, but for an arbitrary number of pictures?


We can, by using recursion.


As a way to start thinking about solving our camera problem using recursion, we'll look at how we might compute factorial so that the result is returned in a completion handler.


The complication is that the final result will need to be passed IN to the handler, rather than simply returned.

The most straightforward method is to do the computation "on the way down" by passing the closure, "as is", down to the base case where it receives the computed factorial as it's argument:

<pre class="lang:swift decode:true">func closureFactorial(N:Int, tempResult:Int, completionHandler:(result:Int) -&gt; ()) {

    if N == 1 {

        completionHandler(result: tempResult) // factorial computed

    } else {

        closureFactorial(N-1, tempResult:N*tempResult, completionHandler:completionHandler)

    }

}</pre>

Since we're doing our multiplications "on the way down", we'll need an additional argument for storing the result.


Is there a way of using backward recursion so we avoid the extra argument?


Backward recursion with completion handlers works somewhat differently:

<pre class="lang:swift decode:true ">func closureFactorial(N:Int, completionHandler:(result:Int) -&gt; ()) {

    if N == 1 {

        completionHandler(result:1) 

    } else {

        // add another wrapper to the closure

        closureFactorial(N-1) { (result) -&gt; () in

            let newResult = result*N

            completionHandler(result:newResult) // passed closure is wrapped

        }

    }

}</pre>

Rather than just passing the handler down to the base case, a handler that computes the complete solution is built by accretion as each recursive call is made. Like an oyster wrapping a pearl, each call to factorial wraps the handler it is passed, then passes that wrapping handler to the next call. Only when execution reaches the base case is the final accreted closure executed.


Returning to our camera example, and applying handler recursion, we get:

<pre class="lang:swift decode:true ">func takePictureSequence(shutterSpeeds:[Double], completionHandler:() -&gt; ()){

    if shutterSpeeds.count == 0 { // The base case

        completionHandler()

    } else {

        let speed = shutterSpeeds[0]

        let newSpeeds = Array(shutterSpeeds[1..&lt;shutterSpeeds.count])

        takePicture(speed) {

            takePictureSequence(newSpeeds, completionHandler:completionHandler)

        }   

    }   

}</pre>

The recursive solution is much nicer and requires no help from GCD:


As it happens, there's no need to pass anything back in the handler (the pictures are simply saved as they're taken) so we applied the forward style. If there were something to return (like file handles for the images), we could just as easily have applied the backward style in order to avoid the additional argument.


Assuming takePicture is now:

<pre class="lang:swift decode:true ">takePicture(shutterSpeed:Double, completionHandler:(fileHandle:Int) -&gt; ())

</pre>

A backward recursion solution would be:

<pre class="lang:swift decode:true ">func takePictureSequence(shutterSpeeds:[Double], completionHandler:(fileHandles:[Int]) -&gt; ()){

    if shutterSpeeds.count == 0 { // base case

        completionHandler(fileHandles:[])

    } else {

        let speed = shutterSpeeds[0]

        let newSpeeds = Array(shutterSpeeds[1..&lt;shutterSpeeds.count])

        takePictureSequence(newSpeeds) { (fileHandles) -&gt; () in

            takePicture(speed) { (fileHandle) -&gt; () in

                let newHandles = fileHandles + [fileHandle]

                completionHandler(fileHandles:newHandles)

            }

        }

    }

}</pre>

<a href="https://en.wikipedia.org/wiki/Recursion_(computer_science)" target="_blank">Recursion</a> is a powerful technique that is made a little bit more hairy by completion handlers. Hopefully, this has been a helpful explanation of how the technique can be used in conjunction with completion handlers in Swift.

func pauseAnimation() {

    guard animationState == .Animating else { return }
    animationState = .Paused
    
    let pausedTime = layer.convertTime(CACurrentMediaTime(), fromLayer: nil)
    layer.speed = 0.0
    layer.timeOffset = pausedTime
}