\documentclass{article}

\usepackage{verbatim}

\usepackage{listings}

\usepackage{amsfonts}

\usepackage{amssymb}

\usepackage{mathtools}

\newcommand{\itab}[1]{\hspace{0em}\rlap{#1}}

\newcommand{\tab}[1]{\hspace{.2\textwidth}\rlap{#1}}

\begin{document}

\lstset{language=C}

\title{Recursion and Applications}

\author{Akshay Raj Verma}

\section{Introduction}

{\bf Definition.} Recursion is method of defining functions where the function self reference.

A recursion consists of two parts:

\begin{enumerate}

\item A base case (or cases)

\item An algorithm which is used to solve instances of smaller problems, until the problem is reduced to its base case.

\end{enumerate}

{\bf Example:} The Fibonacci Sequence is a famous example of a recursive function\\

\hspace{10mm}{\bf Base Case:} \hspace{10mm}$f(0)=0$ and $f(1)=1$

\hspace{10mm}{\bf Formula:} \hspace{11mm} $f(n)=f(n-1)+f(n-2)$ for all $\mathbb{N}$ $ n \geq 2$

In summary recursion is a method of defining a sequence where each successive object in the sequence is defined by the previous object in the sequence. The initial objects are predefined.

\section{Applications in Mathematics}

\begin{center}

\end{center}

As shown by the above sequences solving $f(2)$ requires the use of base cases $f(1)$ and $f(0)$. Once you have the solution to both of them, you apply the Fibonacci Formula to get $f(2)$. This process is again repeated for $f(3)$ which requires the solutions to $f(2)$ which in turn as noted above requires $f(1)$ and $f(0)$. The Fibonacci Formula is again used to solve it, and so on.

We can see the use of recursion in the Fibonacci Sequence in the procedure when in order to solve the Fibonacci Sequence for $n$ we invoke the procedure in order to solve the problem itself.

In conclusion in order to solve the Fibonacci Sequence for $f(n+2)$ using the recursive algorithm above is not possible without first knowing the solutions for $f(n+1)$ and $f(n)$. The Fibonacci formula is used $n+1$ times to acquire the solution for $f(n+2)$.

However the nth sequence of the Fibonacci Sequence can also be produced without the use of recursion by Binet's formula.

{\bf Theorem:} For all n in $\mathbb{N}$ the Fibonacci Number, we denote $F_n$, can be given directly by the Binet Formula($B_n$) as given below:

\begin{center}

$B_n=\frac{1}{\sqrt[]{5}}((\frac{1+\sqrt[]{5}}{2})^n-(\frac{1-\sqrt[]{5}}{2})^n)$

\end{center}

~\\

{\bf Proof:} We will prove Binet's Formula through the use of strong induction.

The Principle of Mathematical Induction states that in order to prove the statement that $F_n=B_n$, for all $\mathbb{N}$, it is sufficient to prove: $B_1=F_1$, and if $B_n=F_n$ is true then, $B_{n+1}=F_{n+1}$.

{\bf Lemma 1.}

If $B_n=F_n$, then for the base cases n=0, 1 $F_0=B_0$ and $F_1=B_1$

{\bf Proof.}

We want to show that $B_0=F_0$ and $B_1=F_1$

\\

For base case $n=0$:

\\

First we substitute $0$ for $n$ $B_0=\frac{1}{\sqrt[]{5}}((\frac{1+\sqrt[]{5}}{2})^0-(\frac{1-\sqrt[]{5}}{2})^0)$

\\

Which is equal to $\frac{1}{\sqrt[]{5}}((1)-(1))$

\\

Therefore $B_0=0$

\\

And so by the Transitive Property $B_0=F_0$

\\

For base case $n=1$:

\\

First we substitute $1$ for $n$ $B_1=\frac{1}{\sqrt[]{5}}((\frac{1+\sqrt[]{5}}{2})^1-(\frac{1-\sqrt[]{5}}{2})^1)$

\\

So $\frac{1}{\sqrt[]{5}}((\frac{1+\sqrt[]{5}}{2})-(\frac{1-\sqrt[]{5}}{2}))$

\\

Which is equal to $\frac{1}{\sqrt[]{5}}(\frac{(1+\sqrt[]{5})-(1-\sqrt[]{5})}{2})$

\\

Therefore $=\frac{1}{\sqrt[]{5}}(\frac{2*\sqrt[]{5}}{2})$

\\

Simplifying further $=\frac{1}{\sqrt[]{5}}(\sqrt[]{5})$

\\

Therefore $B_1=1$

\\

And so by the Transitive Property $B_1=F_1$

For Base Cases $n=0$ and $n=1$, Binet's Formula is true.

{\bf Lemma 2.}1

If Binet's Formula is true for all $k \in {\mathbb N}$ then it is true for $k+1$, for $k>1$.

{\bf Proof.}

To demonstrate Binet's Formula is true for k+1 we must demonstrate that:

\begin{center}

$F_{k+1}=B_{k+1}$

\\

Which is equal to $\frac{1}{\sqrt[]{5}}((\frac{1+\sqrt[]{5}}{2})^{k+1}-(\frac{1-\sqrt[]{5}}{2})^{k+1})$

\end{center}

We can rewrite Binet's Formula in terms of $\alpha$ and $\beta$. $\alpha = \frac{1+\sqrt[]{5}}{2}$ and $\beta = \frac{1-\sqrt[]{5}}{2}$. $\alpha$ can be recognized also as the Golden Ratio. \\

Substituting in $\alpha$ and $\beta$ into Binet's Formula: \begin{center}$B_n=\frac{\alpha^n - \beta^n}{\sqrt[]{5}}$\end{center}

~\\

{\bf Lemma 2.1.} $\alpha+1 = \alpha^{2}$ and $\beta+1=\beta^{2}$

{\bf Proof.}

In order to solve Lemma 2 we want to show that $\alpha+1$=$\alpha^2$ and $\beta+1=\beta^{2}$

\begin{center}

$\alpha+1= \frac{1+\sqrt[]{5}}{2}+1$

$=\frac{1+\sqrt[]{5}}{2}+\frac{2}{2}$

$=\frac{3+\sqrt[]{5}}{2}$

\\

$\alpha^{2} = (\frac{1+\sqrt[]{5}}{2})^{2}$

$=\frac{1+2\sqrt[]{5}+5}{4}$

$=\frac{6+2\sqrt[]{5}}{4}$

$=\frac{3+\sqrt[]{5}}{2}$

\\

~\\

So by the transitive property $\alpha^2 = \alpha+1$

~\\

$\beta+1 = \frac{1-\sqrt[]{5}}{2}+1$

$=\frac{1-\sqrt[]{5}}{2}+\frac{2}{2}$

$=\frac{3-\sqrt[]{5}}{2}$

\\

$\beta^{2} = (\frac{1+\sqrt[]{5}}{2})^{2}$

$=\frac{1-2\sqrt[]{5}+5}{4}$

$=\frac{6-2\sqrt[]{5}}{4}$

$=\frac{3-\sqrt[]{5}}{2}$

\\

~\\

So by the transitive property $\beta^2 = \beta+1$$\blacksquare$

\end{center}

{\bf Conclusion} Now we continue with the proof of Lemma 2.1, and we proceed using the definition of Fibonacci sequence and induction.

\begin{center}

$F_{k+1}=F_{k}+F_{k-1}$

\\

$

Using Lemma 2.1

$=\frac{1}{\sqrt[]{5}}(\alpha^{k+1}-\beta^{k+1}$)

\end{center}

Using the Principle of induction we have shown that $B_n=F_n$ for all $n \in {\mathbb N}$, by proving the Base Cases of n=0 and n=1, then using induction we found that the theory is true for all $n \in {\mathbb N}$ for all $n>1$, by applying the recursive definition of the Fibonacci sequence.

~\\

~\\

{\bf Conclusions:}

\begin{comment}While both formulas for the Fibonacci series give the same results for $n$, from the definition of computational mathematics they are very different. To find Fibonacci series recursively using $F_n$ requires $n-1$ sums or $O(n)$ time in big O notation. To computationally find the solution to $n$ using Binet's Formula would actually takes longer in cases where $n$ is a relatively small number due to the relative complexity of Binet's Formula. However to find the Fibonacci Number for a large $n$ it is faster to use Binet's Formula. The recursive definition for the Fibonacci Sequence however is much more efficient if one wishes to find the Fibonacci Numbers in traversal order from $1$ to $n$.

\end{comment}

\begin{comment}

ToDo: Factorials, Other math stuff (like Catalan numbers) glanced over, Finally Computer Science implementation,Other applications: in nature Fractals

also: recursive humor, recursive acronym: discuss recursion in languages?

\end{comment}

{\bf Example} Factorials are another example of a recursive function defined as $n!$ for all non negative $\mathbb{Z}$

{\bf Base Case} $n=1$, where the factorial of $1$ (denoted $1!)$, is$ 1$.

One can argue that $0!$ is another base case but the $0!=1$ so it is inconsequential.

{\bf Formula} $n! = n * (n-1)!$ for all non negative $\mathbb{Z}$

~\\

{\bf Implementation} \\

\begin{center}

1!=1

\\

2!=2*1!=2

\\

3!=3*2!=6

\\

4!=4*3!=24

\\

5!=5*4!=120

\\

6!=6*5!=720

\\

...

\end{center}

~\\

\begin{comment}Factorials can be defined as the product of all positive $\mathbb{Z}$ less than $n$. In the factorials you can see recursion solving instances of smaller problems when the factorial of $k$ is computed by finding out the factorials of smaller positive $\mathbb{Z}$, like $(k-1)$. And unlike the Fibonacci Sequence, Factorial's base case, $n=1$, is its "terminating condition", or the point where the recursive process ends, so that the recursion does not continue infinitely.

\end{comment}

Factorial, denoted by $n!$, is the product of all positive integers less than or equal to the positive integer $n$. As shown by the process above, we can see repetition in the process the factorial function uses to solve for smaller $\mathbb{Z}$ before building up to the bigger $\mathbb{Z}$.

~\\

\section{Applications in Computer Science}

Recursion is an important element in computer science. Not only can it be used to find mathematical quantities like Factorials, the Fibonacci Sequence but it is also used to create Data Structures to store information, or search through some structures.

\\Below is a program written in Pseudo code to compute factorials:

\begin{lstlisting}

function: factorial

input: an non negative integer n whose factorial will be

computed

output: print factorial(n)

if n is 0 return 1

else return (n * factorial(n-1))

\end{lstlisting}

~\\

{\bf Step by Step Computing for $n=4$}

One way to imagine recursion in Computer Science is like a stack of coins. Each time the function factorial is called a new "coin" is placed on top of the stack. Each "coin" is a version of the function being called except different data is being used. When n=0 however we instead begin to remove the coins, as now the function is no longer being called rather it is returning data. We begin to "remove" the coins, one by one as each coin now "returns" the data instead of calling the function and continues to do so until no more "coins" are left.

A step by step version of the program is shown below:

\begin{enumerate}

\item $n=4$ so $4* factorial(n-1)$

\item $n=3$ so $3* factorial(n-1)$

\item $n=2$ so $2* factorial(n-1)$

\item $n=1$ so $1* factorial(n-1)$

\item $n=0$ so $return 1$

\item Now $n=0$ and no more functions are being called

\item return $1*1$

\item return $2*1$

\item return $3*2$

\item return $6*4$

\item print $24$

\end{enumerate}

~\\A similar program can be written to solve the recursive version of Fibonacci Sequence.

{\bf Writing a program to solve the Fibonacci Sequence}

Below is a program written in the programming language C to solve the Fibonacci Sequence

\begin{lstlisting}

/* Input: non negative integer n.

Output: Fibonacci Number for n.

*/

int fibonacci(int n)

{

if(n=0)

return 0;

else if(n=1)

return 1;

else

return(fibonacci(n-1)+fibonacci(n-2));

}

int main(){

int n;

printf(fibonacci(n));

return 0;

}

\end{lstlisting}

~\\

Use of recursion in code is signified by the $return$ statement calling the the same function it is currently in. In the $int fibonacci$ function we see it in this statement:

\begin{lstlisting}

return(fibonacci(n-1)+fibonacci(n-2));

\end{lstlisting}

~\\

Here the return statement is calling the fibonacci function, not once but twice, as opposed to the factorial program where the return statement would only be calling the factorial function once.

\begin{comment}

n=4

f(3)f(2)

f(

\end{comment}

~\\

As seen in the program above the function fibonacci, unlike the function factorial, is being called to return two separate times: once to calculate the Fibonacci number for $n-1$ and again to calculate the Fibonacci number for $n-2$. The function call to $fibonacci$ is repeated until $n=0$,and $n=1$ are called.

\section{Recursion vs. Iteration}

When considering recursion, we should also consider iteration. Anything done recursively can be done iteratively. But when do we choose one over another. Generally speaking, in computer science, recursion is an easier to read solution than a solution that is written iteratively. While the code may look cleaner and is more concise, what is happening as the program is running may not be as swift.

First, let's consider readibility and consider an iterative Tower of Hanoi implementation. We will assume that a stack called Stack has been created and will be used for the succession of the solution. Furthermore, we will assume each edge case is being handled. And finally, we will assume all the appropriate helper functions have been implemented. Below the iterative step is shown, written in C:

\begin{lstlisting}

public void iterativeHanoi (int numberOfDisks, struct Stack *sourceStack,

struct Stack *transitionStack, struct Stack * finalStack)

{

int i;

int totalMoves;

for (i = numberOfDisks; i >= 1; i--)

{

push(sourceStack, i);

}

for (i = 1; i <= totalMoves; i++)

{

if (i$ % 3 == 1)

{

moveDisks(sourceStack, finalStack);

}

else if (i % 3 == 2)

{

moveDisks(sourceStack, transitionStack);

}

else if (i % 3 == 0)

{

moveDisks(transitionStack, finalStack);

}

}

}

\end{lstlisting}

~\\ Consider the recursive case. Again, we will assume everything around this recursive step is implemented correctly.

\begin{lstlisting}

public void recursiveHanoi (int diskSize, struct Stack *sourceStack, structStack *finalStack, struct Stack *transitionStack)

{

// Base Case

if (diskSize == 0)

{

// done

}

else

{

recursiveHanoi(diskSize - 1, soureStack, transitionStack,

finalStack);

moveDisk(diskSize, finalStack);

recursiveHanoi(diskSize - 1; transitionStack, finalStack,

sourceStack);

}

}

\end{lstlisting}

~\\As we can see from both iterative and recursive implementations, the iterative case is a little more difficult to implement and a little harder to understand. Furthemore, it takes up a of screen space as opposed to the recursive definition.

~\\

\section{Problems with Recursion}

Recursion can be used to make code more readable and more concise. Further on, in mathematics, we can use induction to prove the correctness of recursive code, as we saw with the Binet Formula and Fibonacci Sequence. However in computer science, recursion can cause performance issues in terms of time needed to complete the recursion as well as the memory required to do the recursion. In fact, in order to make recursion better on time and space, we would need to use other methods of programming such as dynamic programming to maximize efficiency.

~\\

So, what makes recursion inefficient? First, let us understand how recursion works when implemented by a compiler.

\\

~\\

To run a recursive function, the compiler creates call stacks and stack frames. A call stack is a data structure that is used by the program to store current information about the subroutines as the program is being executed. The call stack is essential to keep track of how subroutines delegate control once it finishes executing. A call stack is composed of stack frames and a new one is created everytime a subroutines is called. So, in recursion, everytimethe recursive function is called, a new stack from is created.

~\\

The use of stack frames can be memory inefficient and intesive. By creating a new stack frame for each recursive call, more memory is clogged up. There is the risk of having a stack overflow- where the recursive algorithm may run `too deep'- using up so much memory that there is no more memory left resulting in a program crash.Futher on, it is difficult to ascertain how deep the recursive algorithm may run without experiencing a stack overflow. Finally, because a stack is being used to keep track of the recursion, the program is using a lot of resources to maintain the ever growing stack instead of just the calculations, which leads into slower execution times.

\section{Conclusions}

Recursion is an important element of Mathematics and Computer Science, used in everyday programs and calculations. It can allow algorithms (and by extension computer code) to be more concise and readable. In programs that have thousands of lines of code, and poor documentation recursive algorithms allow other programmers to understand the functionality and purpose of the code much more easily than it's iterative counterpart. The Tower of Hanoi code is a good example of recursion concise qualities. Whereas the iterative version took up much more space, the recursive version was far more concise. So while recursion may not be the most efficient method of writing software, it can save a lot of time for a programmer looking at the code for the first time. This allows software projects to be worked on by multiple developers. However in software projects that require programs to be more memory efficient and faster, iterative programming may be a better choice. \\~

Recursion in mathematics allows formulas and algorithms to be concisely written, and may be more easily understood. Strong induction can be used to prove recursive formulas. An example of this is seen in the recursive Fibonacci Sequence and the Binet Formula. The Fibonacci Sequence can be easily taught to someone who has a basic understanding of addition, where as the Binet Formula requires an understanding of far more complex subjects- roots, powers, and fractions. However it would take a lot longer to calculate the Fibonacci Number for a large $n$ through the Fibonacci Sequence than by using the Binet Formula.

\begin{comment} Further on, it is not purely a mathematical construct, it has appearances in nature too. Snowflake patterns, crystals, and leaf patterns contain fractals which are recursive patterns. If you put two mirrors parallel to each other, an infinite number of nested images are created. This is an example of infinite recursion in nature. Although there are non recursive ways to implement otherwise Recursive formulas and/or programs, it is more inefficient to use the non recursive formula in certain cases, than it is to use the recursive, as evidenced by the Binet Formula and the Fibonacci Formula.\end{comment}

\end{document}