# Recursion > The concept factorials can be implemented using recursion: > $a_n! = n * (a_{n-1})!$ **Base Case:** The "exit state" where no more recursive calls are being made **Recursive Call:** The repeatedly called segment that continues until some condition is met ## Recursive Algorithms Both [[Sorting Algorithms#Merge Sort|merge sort]] and [[Sorting Algorithms#Quick Sort|quick sort]] are two common recursive [[sorting algorithms]]. ## Recurrence Relations > [!abstract] **Formal Definition** > A **recurrence relation** for the sequence ${a_n}$ is an equation that expresses $a_n$ in terms of one or more of the previous terms of the sequence ($a_0, a_1,...a_{n-1}$) > a > A sequence is called a *solution* of a recurrence relation if its terms satisfy the recurrence relation. The general goal when solving a recurrence relation problem is to *find the pattern* that occurs as you go deeper into the function calls ### The Fibonacci Sequence > See also: > - [[Sequences#Recursive Sequences|Recursive Sequences]] > [!abstract] Formal Definition > The *Fibonacci sequence*, $F_0,F_1,F_2,...,$, is defined by the initial conditions $F_0,F_1$ and the recurrence relation: > $F_n = F_{n-1} + F_{n-2}$ > for $n=2,3,4,...$ ^fibonocci-sequence