The recursive topic

Quote from: emeralddancer on August 20, 2009, 03:34:24 PM

Recursion, in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition.

The most common implementation in computer programming is a subroutine that calls itself. There's a searching algorithm called "binary search" that computer science students all learn in their algorithms class. It searches for something that is in a sorted list, such as a word in a dictionary. It starts by choosing the item that is in the exact middle of the list, and comparing it to the item being searched for. Depending on whether the item being searched for comes in order before or after the item from the middle of the list, the algorithm chooses the first half or second half of the list. It then invokes itself to search that half. The process continues until either it finds the item being searched for, or the list is down to one item and can't be divided further. The beauty of this algorithm is that, for a computer, it is far faster than a sequential search. For example, if you have a list of 1,000 items, sequential search will on average take 500 attempts. Binary search will always find the searched-for item (or else conclude it isn't in the list) in a maximum of 10 attempts.

I think I must have had my mind distorted by Dr. Seuss' "The Cat in the Hat Comes Back". If you remember, this is the one in which The Cat in the Hat has a smaller cat under his hat, who is called Little Cat A. This cat in turn is wearing a hat, under which he has a still smaller cat named Little Cat B. And so on. Experimental fiction writer John Barth wrote a short story called "Life Story", in which he wrote of a character, who happens to be an author writing a work of fiction. That author is writing of a character, who is an author writing a work of fiction, etc. Barth also recursed the relation in the other direction; he imagined himself (and the scary thing is, I think he actually believes this) to be a character in a work of fiction, who is being written about by a higher-dimension author. That author is in turn a character being written about by an author in a still higher dimension, etc.

This is the part of mathematics that intrigues me. Someone else can have calculus. For me, bring on the abstract algebra, the fields and rings, and the self-referential algorithms. One of my favorite books is a textbook that I found on chaos theory and self-similar structures.