Recursion
In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.
A recursive function definition has one or more base cases, meaning input(s) for which the function produces a result trivially (without recurring), and one or more recursive cases, meaning input(s) for which the program recurs (calls itself).
Addition
$$\begin{eqnarray}
&&add(0, m) &= m \\
&&add(n+1,m) &= add(n,m)+1
\end{eqnarray}$$
Or
$$\begin{equation}
add(n, m)=\left\{
\begin{array}{ll}
m & \text{if } n = 0 \\
add(n-1,m)+1 & \text{if } n > 0
\end{array}
\right.
\end{equation}$$
Factorial
$$\begin{eqnarray}
&&factorial(0) &= 1 \\
&&factorial(n+1) &= (n+1) \times factorial(n)
\end{eqnarray}$$
Or
$$\begin{equation}
factorial(n)=\left\{
\begin{array}{ll}
1 & \text{if } n = 0 \\
n \times factorial(n-1) & \text{if } n > 0
\end{array}
\right.
\end{equation}$$
Fibonacci Numbers
The recurrence satisfied by the Fibonacci numbers is the archetype of a homogeneous linear recurrence relation with constant coefficients (see below). The Fibonacci sequence is defined using the recurrence
\(F_{n}=F_{n-1}+F_{n-2}\)
with initial conditions (seed values)
- \(F_{0}=0\)
- \(F_{1}=1\)
Or
$$\begin{equation}
Fibonacci(n)=\left\{
\begin{array}{ll}
0 & \text{if } n = 0 \\
1 & \text{if } n = 1 \\
fibonacci(n-1)+fibanacci(n-2)&\text{if } n \geqslant 2
\end{array}
\right.
\end{equation}$$
Minimum(\(\{a_1,\dots,a_n\}\))
Let \(\{a_1,\dots,a_n\}\) be a set of elements.
$$\begin{eqnarray}
&&minimum(\{a_1\}) &= a_1 \\
&&minimum(\{a_1,\dots,a_{n+1}\}) &= \min\{minimum(\{a_1,\dots,a_n\}), a_{n+1}\}
\end{eqnarray}$$
Or
$$\begin{equation}
minimum(\{a_1,\dots,a_n\})=\left\{
\begin{array}{ll}
a_1 & \text{if } n = 1 \\
\min\{minimum(\{a_1,\dots,a_{n-1}\}),a_n\} & \text{if } n > 1
\end{array}
\right.
\end{equation}$$
where
$$\min(x,y) = \text{if }x<y\text{ then }x\text{ else }y$$
Summation
$$\begin{eqnarray}
&&sum(\{~\}) &= 0 \\
&&sum(\{a_1,\dots,a_{n+1}\}) &= sum(\{a_1,\dots,a_n\})+a_{n+1}
\end{eqnarray}$$
Or
$$\begin{equation}
sum(\{a_1,\dots,a_n\})=\left\{
\begin{array}{ll}
0 & \text{if } n = 0 \\
sum(\{a_1,\dots,a_{n-1}\})+a_n & \text{if } n > 0
\end{array}
\right.
\end{equation}$$
length: number of digits
Let \(a_1a_2\dots a_n\) be the decimal representation of the number \(a\).
$$\begin{eqnarray}
&&length(a_1) &= 1 \\
&&length(a_1a_2\dots a_{n+1}) &= length(a_1a_2\dots a_n)+1
\end{eqnarray}$$
Or
$$\begin{equation}
length(a_1\dots a_n)=\left\{
\begin{array}{ll}
1 & \text{if } n = 1 \\
length(a_1\dots a_{n-1})+1 & \text{if } n > 1
\end{array}
\right.
\end{equation}$$
Palindrome
Let \(a_1a_2\dots a_n\) be the decimal representation of the number \(a\).
$$\begin{eqnarray}
&&palindrome(~) &= 1 \\
&&palindrome(a_1) &= 1 \\
&&palindrome(a_1a_2\dots a_{n+2}) &= (a_1=a_{n+2}) \wedge palindrome(a_2\dots a_{n+1})
\end{eqnarray}$$
Let \(len = length(a)\)
$$\begin{eqnarray}
&&palindrome(a, len) &= 1& \text{if } len \leqslant 1 \\
&&palindrome(a_1a_2\dots a_{n+2}, len) &= (a_1=a_{n+2}) \wedge palindrome(a_2\dots a_{n+1},len-2)& \text{if } len \geqslant 2
\end{eqnarray}$$
$$\begin{equation}
palindrome(a_1\dots a_n)=\left\{
\begin{array}{ll}
1 & \text{if } n \leqslant 1 \\
\text{if }a_1=a_n\text{ then } palindrome(a_2\dots a_{n-1})\text{ else } 0& \text{if } n \geqslant 2
\end{array}
\right.
\end{equation}$$
Linear Search
Let \(a[lo, hi)\) denote half close half open interval of an array, i.e. it consists of \(a[lo], a[lo+1], ..., a[hi-1]\). In case of \(lo = hi\), that means it is an empty array.
$$\begin{equation}
lsearch(x, a[lo, hi))=\left\{
\begin{array}{ll}
-1 & \text{if } lo = hi\\
\text{if }x = a[lo] \text{ then }lo \text{ else }lsearch(x, a[lo+1, hi)) & \text{otherwise}
\end{array}
\right.
\end{equation}$$
Binary Search
Let \(a[lo, hi)\) denote half close half open interval of an array.
$$\begin{equation}
bsearch(x, a[lo, hi))=\left\{
\begin{array}{ll}
-1 & \text{if } lo = hi\\
mid & \text{if }x = a[mid] \\
bsearch(x, a[lo, mid)) & \text{if }x < a[mid]\\
bsearch(x, a[mid+1, hi)) & \text{if }x > a[mid]
\end{array}
\right.
\end{equation}$$
where
\(mid = \frac{lo+hi}{2}\) with integer division.
$$\begin{equation}
bsearch(x, a[lo, hi))=\left\{
\begin{array}{ll}
-1 & \text{if } lo = hi\\
\text{if }x = a[mid] \text{ then }mid & \text{otherwise}\\
\text{ else if }x < a[mid] \text{ then } bsearch(x, a[lo, mid)) \\\text{ else }bsearch(x, a[mid+1, hi))
\end{array}
\right.
\end{equation}$$
Sort
The result of sorting function \(sort(a[lo,hi)\) itself is an array such that
$$sort(a[lo,hi))[i] < sort(a[lo,hi))[j] \text{ for all } lo\leqslant i<j<hi$$.
Minindex(\(a[lo,up)\))
Find out the index of the minimum element in array \(a[lo,hi)\).
$$\begin{equation}
minindex(a[lo,hi))=\left\{
\begin{array}{ll}
lo & \text{if } lo+1 = hi \\
mindex\{a[minindex(a[lo+1,hi))],a[lo]\} & \text{if } lo+1<hi
\end{array}
\right.
\end{equation}$$
where
$$mindex(a[i],a[j]) = \text{if }a[i]<a[j]\text{ then }i\text{ else }j$$
Swap(\(a[lo,up),i,j\))
\(swap(a[lo,up),i,j)\) itself is an array such that:
$$\begin{equation}
swap(a[lo,up),i,j)[k]=\left\{
\begin{array}{ll}
a[lo,up)[k] & \text{if } k \notin \{i,j\} \\
a[lo,up)[j] & \text{if } k = i \\
a[lo,up)[i] & \text{if } k = j
\end{array}
\right.
\end{equation}$$
Selection Sort
Based on two previous functions, we can derive recursive selection sort function.
$$\begin{equation}
ssort(a[lo,up))=\left\{
\begin{array}{ll}
a[lo,up) & \text{if } lo+1 = hi \\
ssort(swap(a[lo,hi),lo,minindex(a[lo,hi)))[lo+1,hi)) & \text{otherwise}
\end{array}
\right.
\end{equation}$$
B1pass
Bubbling one pass will make \(b1pass(a[lo,up)[lo] < b1pass(a[lo,up)[i]\) for all \(i \in (lo,hi)\).
$$\begin{equation}
b1pass(a[lo,up))=\left\{
\begin{array}{ll}
a[lo,up) & \text{if } lo+1 = hi \\
\text{if }b1pass(a[lo+1,hi)[lo]<b1pass(a[lo+1,hi)[lo+1]& \text{otherwise}\\
\text{ then }b1pass(a[lo+1,hi))\\
\text{ else }swap(b1pass(a[lo+1,hi)),lo,lo+1)
\end{array}
\right.
\end{equation}$$
Bubble Sort
$$\begin{equation}
bsort(a[lo,up))=\left\{
\begin{array}{ll}
a[lo,up) & \text{if } lo+1 = hi \\
bsort(b1pass(a[lo,hi))[lo+1,hi))& \text{otherwise}
\end{array}
\right.
\end{equation}$$
Merge Sort
to be continued...
