Taming Recursion - Introduction

Taming Recursion - Introduction.md

Taming Recursion - An Introduction

[[Image]]

Recursion, which ends up being way simpler for some problems, can seem very hard for you to wrap your head around, or to follow down the recursive rabbit-hole to understand how it produces the values it does (spoiler: doing this may be a mistake).

But do not despair, I'm here to help you learn a very good framework to think recursively in any programming language and almost any problem.

Every code example will be in Scala a programming language that combines the object-oriented and functional programming paradigms. It will be very straightforward to translate the examples from Scala to your language of choice since the syntax is very much approachable.

Motivation

• Talk about relevance of FP and how languages that use it rely on recursion
• Talk about problems and data structures that are easier to solve/traverse with recursion rather than iteration
• Show some cool problems we're going to learn to solve using recursion
  • Pyramid and Inverted pyramid
  • Binary Tree Drawing without/with Lines
  • Fractals
  • Tic-Tac-Toe Solver

A Methodic Way to Learn Recursion

In this series of writings you'll see a very methodic way to think about recursion and recursive problems. This methodology involves the following set of basic disciplines below.

• Function Templating & Design
• Data Design
• Reasoning About Self-Referential Data
• Writing Recursive Functions that Operate on Self-Referential Data
• Writing Recursive Functions that Operate on Generative Data

But I do think reasonable to clarify to you, at least, why you should bother to acquire these disciplines. Why not just go straight to the point and see some code to to understand synthesize recursion in your head?

It's very simple: you need to internalize some foundational concepts and rewire your brain, step-by-step, in order to see recursion through a new lens, hopefully with less of the bias carried from imperative programming and iteration (for, while, etc).

[Brain Rewring Image]

Therefore, I kindly ask for your patience. Hang there for a bit, follow these practice methodically and you'll be surprised at how much easier it is to write recursive functions, and more importantly, compose large programs from smaller functions step-by-step.

[Patience Illustration]

Function Templating & Design

Before diving into recursion, I feel that it is important for you to acquire the discipline of thinking about the "form" and behavior of functions even before writing them — what we call function templating. That discipline involves:

• Writing what types the function consumes and produces (you don't need to write those in a typed language, but it is still useful to think on what types you want)
• Writing a short and conscise text of what the function does based on its input
• Writing a simple version of the function that produces a dummy result, so we can test our unit tests
• Writing unit tests for the function
• Replacing the stub with a template of the function
• Implement and debug the correct version of the function, running the tests to be sure that it works

As we will see, this discipline makes it very straightforward to reason about functions, to write programs with many function, and to debug them with less time.

A very really simple function code that illustrates the ideia:

/**
 * produces the factorial of n
 */
def factorial(n: Int): Int = {
  if (n == 0)
    1
  else 
    n * factorial(n - 1)
}

In dynamic-typed languages like Python and Ruby, we would include the types that the function consumes and produces in the comment:

# int -> int
# produces the factorial of n
def factorial n
  if n == 0 then 1
  else n * factorial (n - 1)
  end
end

Data Design

Quite similar to function design, we'll also get to describe the custom data types we will create. This will be very useful to understand self-referential data — which is a kind of data that refers back to itself.

xyz

Reasoning about Self-Referential Data

Modeling Functions Operating on Self-Referential Data

---

Why should you bother about doing the rituals described above just to write functions? Well, we have many important reasons, more so in the context of programs with many functions:

• It makes it very easy to reason about functions
• It decreases debugging pain
• We end up creating "muscle" memory to easily write functions that operate on some form of data (e.g. trees, graphs, lists, etc) —— which ends up being very important to understand recursion.

In the next text we're going to learn to write some simple recursive functions that operate on the most basic self-referential data type I know of — natural numbers.