Posted on Leave a comment

The Three Laws of Recursion

Like the robots of Asimov, all recursive algorithms must obey three important laws:

  • A recursive algorithm must have a base case.
  • A recursive algorithm must change its state and move toward the base case.
  • A recursive algorithm must call itself, recursively.

Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself. For example, we can define the operation “find your way home” as: If you are at home, stop moving. Take one step toward home.

Let’s begin our discussion of recursion by examining the first appearance of fractals in modern mathematics. In 1883, German mathematician George Cantor developed simple rules to generate an infinite set:

Cantor’s rule for an infinite set

There is a feedback loop at work here. Take a single line and break it into two. Then return to those two lines and apply the same rule, breaking each line into two, and now we’re left with four. Then return to those four lines and apply the rule. Now you’ve got eight. This process is known as recursion: the repeated application of a rule to successive results. Cantor was interested in what happens when you apply these rules an infinite number of times.

George Cantor

Dichotomy paradox – Zeno’s

“That which is in locomotion must arrive at the half-way stage before it arrives at the goal.”

— as recounted by Aristotle, Physics VI:9, 239b10

Suppose Atalanta wishes to walk to the end of a path. Before she can get there, she must get halfway there. Before she can get halfway there, she must get a quarter of the way there. Before traveling a quarter, she must travel one-eighth; before an eighth, one-sixteenth; and so on.

Zeno’s paradox was recursive by cutting the distance in half each time to the infinitesimal. This is also how the Tortoise beat the Hair by questioning time over distance.

Recursive Function Calls

The tortoise and the Hair – the paradox of time
int factorial(int n) 
{ if (n == 1) { return 1; }
else { return n * factorial(n-1); } }

A function that does call others is called a nonleaf function. … The factorial function can be rewritten recursively as factorial(n) = n × factorial(n – 1). The factorial of 1 is simply 1. The image shows an object trace of the factorial function written as a recursive function. Each call goes in the run time stack until the base case is reached, and the the stack is popped as the result is passed to each function on the stack.

Five Factorial (5!) in recursion

What Is a Fractal?

The term fractal (from the Latin fractus, meaning “broken”) was coined by the mathematician Benoit Mandelbrot in 1975. In his seminal work “The Fractal Geometry of Nature,” he defines a fractal as “a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reduced-size copy of the whole.”

Recursion in Nature

Looking closely at a given section of the tree, we find that the shape of this branch resembles the tree itself. This is known as self-similarity; as Mandelbrot stated, each part is a “reduced-size copy of the whole.”

The Three Laws of Robotics

Isaac Asimov was an American writer and professor of biochemistry at Boston University. During his lifetime, Asimov was considered one of the “Big Three” science fiction writers, along with Robert A. Heinlein and Arthur C. Clarke. A prolific writer, he wrote or edited more than 500 books.

  • A robot may not injure a human being or, through inaction, allow a human being to come to harm
  • A robot must obey the orders given it by human beings except where such orders would conflict with the First Law
  • A robot must protect its own existence as long as such protection does not conflict with the First or Second Laws
Partial sources: https://natureofcode.com/book/chapter-8-fractals/, Wikipedia, Google 
Posted on Leave a comment

How My Little Pony turned a little girl into a computer scientist

I had several small plastic Ponies that I used to play make-believe with my friends. But I had one larger, plush My Little Pony, a bright-green stuffed horse with a vivid pink mane and tail that I played with all by myself. I would sit for hours on my own, braiding and rebraiding its tail. I developed a system for braiding the tail of my Pony that taught me about mathematical concepts– from division to recursion.

Continue reading How My Little Pony turned a little girl into a computer scientist