arts102 Research


2005F		ARTST 102 Algorithmic Visualization Michael Bokosky Recursion
Research Topic		Recursion, Recursive Algorithms, Fractals
Description		In mathematics and computer science, recursion is a particular way of specifying or constructing a class of objects or an object from a certain class with the help of a reference to other objects of the class: a recursive definition defines objects in terms of the already defined objects of the class. An algorithm is defined as a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a corresponding recognizable end-state (1) A recursive algorithm is an algorithm that calls itself with smaller input values, and obtains the result for the current input by applying simple operations to the returned value for the smaller input. In a recursive algorithm, the output of a process is fed back in as the new input to the process. One can use a recursive algorithm more generally to solve a problem, if that problem can be solved by utilizing solutions to smaller versions of the same problem. The elements of a recursively defined set, or the value of a recursively defined function can be obtained by a recursive algorithm. In general, recursive computer programs require more memory and computation compared with iterative algorithms, but they are simpler and for many cases a natural way of thinking about the problem. (2) In 1975 Benoit Mandelbrot coined the term fractal to describe self-similar shapes achieved by the process of recursion. Self-similar shapes can be defined as shapes that you can zoom in and out of and will ultimately appear the same. Fractals are useful in describing many types of naturally occurring stuctures that are complex in nature such as snowflakes, trees, coastlines, mountains, etc. Fractals are used and perhaps overused in general and for their aesthetic quality.(3)

Examples/Links Recursive Tree		Ex.1 Natural Numbers recursive definition of N: 0, 1 are in N; if n and n + 1 are in N, then n + 2 is in N; N is the smallest set satisfying the previous two properties. __________________________________________________________________ Ex.2 Simple recursive algorithm: Algorithm 1: Even(positive integer k) Input: k , a positive integer Output: k-th even natural number (the first even being 0) Algorithm: if k = 1, then return 0; else return Even(k-1) + 2 . __________________________________________________________________ Recursion1 Recursion2 Recursive Tree Koch Fractals 2
References/Links		(1) http://en.wikipedia.org/wiki/Recursive_algorithm#Recursive_algorithms (2) http://www.cs.odu.edu/~toida/nerzic/content/recursive_alg/rec_alg.html (3) http://www.shiffman.net/itp/classes/nature/week07/