Explaining recursion to a ghost

I had an imaginary conversation with my mom the other day. Sometimes that happens when you lose people you love. You imagine them when they aren’t there and you think about what they would say or do. Obviously, it’s just a fragment of them, but sometimes it helps you get through extremely painful moments.

This time though, the conversation arrived as easy as complimentary dinner rolls. I was imagining my mother hearing about my newest coding endeavor that seemed to be sticking. It wasn’t another fluke, I wanted to tell her. It was something to be proud of. It would save lives.

In my vision, like I had before she died, I snuggled into her side on the old red couch with my laptop. I opened Visual Studio Code and she cooed at how pretty the font ligatures made the arrows and squiggles look. I told her it was simple really, which it was, and showed her some data types. I even made example ones on the fly so her eyes could adjust to something familiar:

type pie = 
| Apple
| Cherry
| KeyLime
| BananaCream
| Rhubarb

She jokes in my vision that coding is making her hungry. I tell her we’ll go to Dairy Queen after she sees the rest of it. She comes across a recursive type and I can see her brow furrow in confusion. I mention the word gently, knowing it will make her feel overwhelmed: recursion. Timidly, I begin to explain a problem…

Imagine you are attempting to give a blind man a recipe for descending stairs safely. You could help him a couple different ways. You could take the approach of actually counting how many stair steps there were from top to bottom and telling him to step down that number exactly.

let step ?step_number:(n=25) () =
    let i = ref n in
    while !i <> 0 do
        decr i;
        print_endline @@ "Stepping down to " ^ (string_of_int !i)
    done
in step()

This approach basically works. The only problem is it’s rather brittle. For one, it only really works on his staircase. It’s not going to work on any other staircase unless they are the same step number. Fatally, if you attempt this technique on a differently-numbered staircase you will either be left in the middle or potentially fall on your face. In programming, we call this approach to a solution “an Imperative approach.”

There is another way of approaching this problem, I say to her. The declarative approach: One simply instructs the blind man to slide a foot forward until he hits a ledge. If he does, he should step down. If he feels no ledge, then he has reached the bottom of the steps.

type step =
| Bottom
| Ledge of step

My mother furrows her brow a bit and says, “But that is too simple.” She should have been a coder. Yes, I’m sure abnormally large stair widths would probably become a problem worth testing for. Fearing my analogy is sliding off the rails, “Note, the constraints and structure of determining if you should step down are repeatable and work no matter the number of stairs. The larger structure of how you descend a staircase here looks the same in a smaller scale at every step.”

let rec descend =
  function
  | Bottom -> ()
  | Ledge step -> 
      print_endline "Stepping down...";
      descend step

She lights up like a Christmas bulb, “Like those pretty succulents in the store!”

“Yes, you got it. Fractal patterns are recursive and all over nature. The big structure looks the same as the smallest part of that structure.”

Like you and me, she’d say. Alone in my office, typing to you in the dark, I marvel at the structure. One iteration to the next chained together through time. A ghost explained to me how computer science related to the continuation of women who came before me and women who would come after me.

“They made me go to school for home economics” she said, a sparkle in her eye. Her blond wavy hair began to glitter and disappear as if she were powder blown off the slate of existence.

“And now look at you.”