# Recursion

 related topics {math, number, function} {food, make, wine} {language, word, form} {theory, work, human} {god, call, give} {film, series, show} {woman, child, man} {build, building, house} {style, bgcolor, rowspan}

Recursion, in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition; specifically it is defining an infinite statement using finite components. The term is also used more generally to describe a process of repeating objects in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion.

## Contents

### Formal definitions of recursion

In mathematics and computer science, a class of objects or methods exhibit recursive behavior when they can be defined by two properties:

For example, the following is a recursive definition of a person's ancestors:

• One's parents are one's ancestors (base case).
• The parents of one's ancestors are also one's ancestors (recursion step).

The Fibonacci sequence is a classic example of recursion:

• Fib(0) is 0 [base case]
• Fib(1) is 1 [base case]
• For all integers n > 1: Fib(n) is (Fib(n-1) + Fib(n-2)) [recursive definition]

A convenient mental model of recursion defines the recursive object (whether that object is an equation, an algorithm, an image, or a rule) in terms of "previously defined" objects of the same class. For example: How do you move a stack of 100 boxes? Answer: you move one box, remember where you put it, and then solve the smaller problem: how do you move a stack of 99 boxes? Eventually, you're left with the problem of how to move a single box, which you know how to do.