How to Think Recursively?

Twin Functions

Let’s meet Danial and Narciss. They are twins, with exactly the same behavior!

stateDiagram
    A --> Danial
    A --> Narciss
    Danial --> B
    Narciss --> B

Same behavior means you cannot distinguish them based on their input and output.

Now, let’s say Danial and Narciss are f(x) = x + 1.

If you are a functional style lover, you may call it (+1). All functions are single input in functional style. For more details, you can search about Currying and UnCurrying functors in category theory.

We give Danial a 1 and ask him to pass it to Narciss and ask her to pass it to Danial again. What will happen?

sequenceDiagram
  We -->> Danial: 1
  Danial -->> Narciss: 2
  Narciss -->> Danial: 3
  Danial -->> Narciss: 4
  Narciss -->> Danial: 5
  Danial -->> Narciss: 6
  Narciss -->> Danial: 7
  Danial -->> Narciss: 8

And it will go on forever, right? It really sounds familiar, like an infinite loop, right? So something like the loop condition is missing here!

Hmm, maybe we can ask Danial and Narciss to check the number every time, and if the number is smaller than 10, they do their normal behavior, but if the number is 10 or bigger than 10, give the number back to us.

So now, we can define Danial and Narciss as:

graph LR
A[1] --> B{1 < 10?}
B --> |Yes| C[+ 1]
B --> |No| D[Return]

Now what will happen? Now we have a state, which we do not want to continue!

sequenceDiagram
  We ->> Danial: 1
  opt a < 10
    Danial -->> Narciss: 2
    Narciss -->> Danial: 3
    Danial -->> Narciss: 4
    Narciss -->> Danial: 5
    Danial -->> Narciss: 6
    Narciss -->> Danial: 7
    Danial -->> Narciss: 8
    Narciss -->> Danial: 9
  end
  opt a == 10
    Danial -->> Narciss: 10
    Narciss ->> We: 10
  end

Nice! We have 10! instead of a stack overflow 😂.

Let’s now imagine another scenario, functions as types.

Can we see functions as types? 🤔

Let’s start with addition. As you know, + is a function in math, which accepts two inputs and gives us an output of the same type as the inputs.

graph LR
A[A::Int] --> C(Sum::Int->Int->Int)
B[B::Int] --> C(Sum::Int->Int->Int)
C(Sum::Int->Int->Int) --> D[D::Int]

Huh? How can it accept two parameters? Danial, you’ve mentioned

All functions accept only 1 parameter.

But now, the sum function is accepting 2 inputs. How?

stateDiagram
    A --> Sum
    B --> Sum
    Sum --> C

I understand your POV. Wait for my blog on Curry and Uncurry functors. I’ll explain it. 😉

Let’s for now focus on functions as types. Functions are types, but you cannot evaluate them completely.

Wait a minute, functions are types, so we have recursive types? Exactly!

Consider a Binary Tree!

stateDiagram
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
    D --> R
    R --> N
    R --> P
    D --> J
    E --> Null
    E --> M

Can you see the repetitive pattern?

stateDiagram
    Mom --> LeftChild
    Mom --> RightChild

Hmm, interesting. Now we can say in a binary tree, we have a type node, which is either a mom or a child, right?

• A mom has 2 children and some kind of data.
• A child is a leaf node; they only contain some kind of data.

So we can say:

BinaryTreeNode = Mom of Int * BinaryTree * BinaryTree | Child of Int

stateDiagram
    Node --> Mom
    Node --> Child
    Child --> Data
    Mom --> Child
    Mom --> Child
    Mom --> Data

Sounds cool, right?

You probably heard about JSON, right? It’s also a recursive data type!

Object: A set of key * values Array: Collection of values

stateDiagram
  Object --> Key
  Object --> Value
  Value --> Object
  Value --> Listof
  Value --> String
  Value --> Int
  Value --> Bool
  Listof --> Object
  Listof --> String
  Listof --> Int
  Listof --> Bool

Thanks for your attention, friends. I’ll publish an article about how to solve problems recursively next week. Stay tuned!