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:
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.
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
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.
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.”
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
