A divide and conquer problem solving method is a top-down method that breaks a problem into smaller parts, solves each smaller part, and combines the solution (in a bottom-up manner) to solve the original problem.

Decomposition is breaking something down into smaller parts.

Examples:

• divide and conquer problem solving strategy
• soil decomposition is breaking down of the soil

Composition is putting parts together to form larger entities.

Examples:

• English composition
• musical composition (composer)
• functional composition in math:

A recursive definition is a definition that is defined in terms of itself.

The mathematical term "reflexive" is used to define something in terms of itself.

That is, the value x, whatever x is, is equal to itself (in a reflexive relation sense).

In more technical terms, a binary relation R over a set X is reflexive if every element of set X is related using the relation R to itself (in a true manner).

This definition becomes important in later courses such as algorithms and data structures.

Consider the relation "is the same sex/gender as".

Although there have been issues in the news about what "gender" really is, one should find agreement that whatever the gender is of a person, that that person has the same gender as that person. That is, it is a reflexive property.

Have you ever heard someone say "do as I say, not as I do"? That is, the rule applies to others and not to oneself. That is, the rule is not reflexive.

Have you ever sent a email message to yourself?

Did you then receive an email message from yourself?

That is, you were sending email reflexively.

A common saying/symbol for self-reference is the snake eating it's tail.

The ancient symbol of Ouroboros, via the Greek ουροβόρος for "tail" and "food", originated in Egyptian symbology.

Cats often can be tempted into chasing and trying to bite their own tail.

Have you ever sent a self-addressed envelope?

Now how is an envelope supposed to address itself?

One can self-address ones-self with the words "I" or "me".

Why is recursion so important to computer science?

In all fields, some things give a person a competitive advantage.

• Basketball: dunk a basketball
• Music: perfect pitch
• Computer science: recursion

In each field, you can still succeed, but having certain skills results in a huge advantage compared to someone who does not have that skill.

In computer science, one can work hard and learn how to think and program recursively, but it takes some mental time and effort and practice.

A more elegant statement of a recursive self-referential principle is Hofstadter's Law.

Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law. Hofstadter, D. (1979). Goedel, Escher, Bach: An eternal golden braid. New York: Vintage Books., p. 152.

Something is recursive if it directly or indirectly refers to itself.

• Is no your answer to this question?
• The next sentence is true. The previous sentence is false.

Problems sometimes result if the recursive relationship is circular.

A procedure or function is recursive if the procedure and/or function calls itself either directly or indirectly.

Remember the message passing model.

A recursive definition is a definition that refers to itself in some way

Dictionary definition:

re-cur-sive. adjective. referring to itself. see recursive.

The use of recursion provides a powerful design and implementation strategy that is, in essence, a divide and conquer problem solving strategy.

• Divide a big problem into smaller problems
• Solve each smaller problem (recursively if needed)
• But together the solutions to the smaller problems to solve the bigger problem.

Acronyms can be recursive, such as the acronym GNU (GNU is Not Unix) . (gcc compiler)

An Acronym can describe itself in some way, such as a TLA (Three Letter Acronym) . Note that a TLA is a TLA .

A recursive algorithm or definition is circular, but also, to be well defined, needs to refer to a smaller instance if itself. One example is a set of Russian Matryoshka (матрёшка) dolls.

Recursive definitions are powerful methods to allow a rule or rules to handle smaller instances of themselves.

Fractals are self-similar objects. As one zooms in on a fractal, it can appear endless.

Two Koch snowflakes of different orders can be used to tessellate (i.e., fill) the plane.


Note: It is possible to use more than two sizes of snowflakes to tessellate the plane.

Recursive rules apply to parts of imperative programs, though it is not as obvious.

Consider the while loop defined in pseudo-code as follows.

The above while loop can be defined (as in a macro expansion) as follows.

The expansion can go on until the while loop is complete. This is sometimes call loop unrolling (in, say, code optimization techniques).

This sentence is false!

The previous sentence refers to itself (while this sentence refers to another sentence).

Note that language (and programming languages) can inherently refer to itself, directly or indirectly.

Such references can be mutually recursive (or circular).

A circular argument or circular reasoning never ends, or creates a paradox.

Which came first, the chicken or the egg?

Such paradoxes are central to computability and information theory in computer science and information theory.

Def: Recursive. Adjective. Something that refers to itself. See Recursive.

Recursive: something that refers to a smaller instance of itself (to insure termination), as opposed to something that is circular (does not terminate).

For a mutually recursive set of functions to terminate, each recursive call must be to a smaller instance (in some sense) of the overall problem.

1 questions omitted (login required)

2 acronyms omitted (login required)