\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
\else % if luatex or xelatex
  \ifxetex
    \usepackage{mathspec}
  \else
    \usepackage{fontspec}
  \fi
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\usepackage[unicode=true]{hyperref}
\hypersetup{
            pdftitle={CSci 555, Functional Programming Recursion Concepts and Terminology: Scala Version},
            pdfauthor={H. Conrad Cunningham},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi
\usepackage{caption}
\DeclareCaptionLabelFormat{nolabel}{}
\captionsetup{labelformat=nolabel}

\title{CSci 555, Functional Programming\\
Recursion Concepts and Terminology:\\
Scala Version}
\author{H. Conrad Cunningham}
\date{10 February 2016 (minor formatting updates 3 August 2016)}

\begin{document}
\maketitle

{
\setcounter{tocdepth}{4}
\tableofcontents
}
Copyright (C) 2016, H. Conrad Cunningham

\textbf{Acknowledgements}: I adapted the factorial, Fibonacci number,
and exponentiation functions used below from the
\href{SICP_examples/Scal/}{Scala functional programming examples}
developed for this class based on similar
\href{SICP_examples/Elixir/}{Elixir programs}, which, in turn, were
adapted from similar \href{SICP_examples/Lua/}{Lua programs}, which, in
turn, were adapted from the Scheme programs in Abelson and Sussman's
classic \href{http://mitpress.mit.edu/sicp/}{SICP textbook}. This set of
notes was also adapted from a version using Elixir examples.

\section{Recursion Concepts and
Terminology}\label{recursion-concepts-and-terminology}

\subsection{Linear and Nonlinear
Recursion}\label{linear-and-nonlinear-recursion}

\subsubsection{Linear recursion}\label{linear-recursion}

A function definition is \emph{linear recursive} if at most one
recursive application of the function occurs in a leg of the definition
(i.e., along a path from an entry to a return). The various function
clauses and branches of the conditional expressions \texttt{if} and
\texttt{match} introduce a path.

The definition of the function \texttt{factorial} below is linear
recursive because the expression in the second leg of the definition
(i.e., \texttt{n\ *\ factorial(n-1)}) involves a single recursive
application. The other leg is nonrecursive; it is the base case of the
recursive definition.

\begin{verbatim}
    def factorial(n: Int): Int = n match {
      case 0          => 1
      case m if m > 0 => m * factorial(m-1)
    }
\end{verbatim}

Scala checks for pattern matches for the clauses in the order given in
the function definition. It executes the leg corresponding to the first
successful match. If no pattern matches, then the function aborts and
displays an error message.

\subsubsection{Time and space
complexity}\label{time-and-space-complexity}

How efficient is function \texttt{factorial}?

Function \texttt{factorial} recurses to a depth of \texttt{n}. It thus
has \emph{time complexity} O(\texttt{n}), if we count either the
recursive calls or the multiplication at each level. The \emph{space
complexity} is also O(\texttt{n}) because a new runtime stack frame is
needed for each recursive call.

\subsubsection{Termination of recursion}\label{termination-of-recursion}

How do we know that function \texttt{factorial} terminates?

To show that evaluation of a recursive function terminates, we must show
that each recursive application \emph{always} gets closer to a
termination condition represented by a base case. For a call
\texttt{factorial(n)} with \texttt{n\ \textgreater{}\ 0}, the argument
of the recursive application always decreases to \texttt{n\ -\ 1}.
Because the argument always decreases in integer steps, it must
eventually reach 0 and, hence, terminate in the first leg of the
definition.

\subsubsection{Preconditions and
postconditions}\label{preconditions-and-postconditions}

The \emph{precondition} of a function is what the caller (i.e., the
client of the function) must ensure holds when calling the function. A
precondition may specify the valid combinations of values of the
arguments. It may also record any constraints on the values of
``global'' data structures that the function access or modifies.

If the precondition holds, the supplier (i.e., developer) of the
function must ensure that the function terminates with the
\emph{postcondition} satisfied. That is, the function returns the
required values and/or alters the ``global'' data structures in the
required manner.

The precondition of the \texttt{factorial} function requires that
argument \texttt{n} be a nonnegative integer value. We could use Scala's
predefined \texttt{requires} method to ensure this precondition holds,
but, in this version, if all pattern matches fail, then the function
call aborts with a standard error message.

The postcondition of \texttt{factorial} is that the result returned is
the correct mathematical value of \texttt{n} factorial. The function
\texttt{factorial} neither accesses nor modifies any global data
structures.

\subsubsection{Nonlinear recursion}\label{nonlinear-recursion}

A \emph{nonlinear recursion} is a recursive function in which the
evaluation of some leg requires more than one recursive application. For
example, the naive Fibonacci number function \texttt{fib} shown below
has two recursive applications in its third leg. When we apply this
function to a nonnegative integer argument greater than 1, we generate a
pattern of recursive applications that has the ``shape'' of a binary
tree. Some call this a \emph{tree recursion}.

\begin{verbatim}
    def fib(n: Int): Int = n match {
      case 0           => 0
      case 1           => 1
      case m if m >= 2 => fib(m-1) + fib(m-2) // double (tree) recursion
    }
\end{verbatim}

Termination: How do we know that \texttt{fib} terminates?

Complexity: Function \texttt{fib} is combinatorially explosive, having a
time complexity O(\texttt{fib\ n}). The space complexity is
O(\texttt{n}) because a new runtime stack frame is needed for each
recursive call and the calls recurse to a depth of \texttt{n}.

An advantage of a linear recursion over a nonlinear one is that a linear
recursion can be compiled into a \emph{loop} in a straightforward
manner. Converting a nonlinear recursion to a loop is, in general,
difficult.

\subsection{Backward and Forward
Recursion}\label{backward-and-forward-recursion}

\subsubsection{Backward recursion}\label{backward-recursion}

A function definition is \emph{backward recursive} if the recursive
application is embedded within another expression. During execution, the
program must complete the evaluation of the expression after the
recursive call returns. Thus, the program must preserve sufficient
information from the outer call's environment to complete the
evaluation.

The definition for the function \texttt{factorial} above is backward
recursive because the recursive application \texttt{factorial(n-1)} in
the second leg is \emph{embedded within the expression}
\texttt{n\ *\ factorial(n-1)}. During execution, the multiplication must
be done after return. The program must ``remember'' (at least) the value
of parameter \texttt{n} for that call.

A compiler can translate a backward linear recursion into a loop, but
the translation may require the use of a stack to store the program's
\emph{state} (i.e., the values of the variables and execution location)
needed to complete the evaluation of the expression.

\subsubsection{Forward recursion}\label{forward-recursion}

A function definition is \emph{forward recursive} if the recursive
application is \emph{not embedded within another expression}. That is,
the \emph{outermost expression is the recursive application} and any
other subexpressions appear in the argument lists. During execution,
significant work is done as the recursive calls are made (e.g., in the
argument list of the recursive call).

The definition for the auxiliary function \texttt{factIter} within the
\texttt{factorial2} definition below is forward recursive. The recursive
application \texttt{factIter(n-1,n*r)} in the second leg is on the
outside of the expression evaluated for return. The other legs are
nonrecursive.

\begin{verbatim}
    def factorial2(n: Int): Int = {

      def factIter(n1: Int, r: Int): Int = n1 match {
        case 0          => r
        case m if m > 0 => factIter(m-1,m*r)
      }
                    
      factIter(n,1)
    }
                
\end{verbatim}

Termination: How do we know that \texttt{factIter} terminates?

Complexity: Function \texttt{factorial2} has a time complexity
O(\texttt{n}). But, because, tail call optimization converts the
\texttt{factIter} recursion to a loop, the time complexity's constant
factor should be smaller than that of \texttt{factorial} and the space
complexity of \texttt{factIter} is O(1).

\subsubsection{Tail Recursion}\label{tail-recursion}

A function definition is \emph{tail recursive} if it is \emph{both
forward recursive and linear recursive}. In a tail recursion, the last
action performed before the return is a recursive call.

The definition of the function \texttt{factIter} above is tail recursive
because it is both forward recursive and linear recursive.

Tail recursive definitions are easy to compile into efficient loops.
There is no need to save the states of unevaluated expressions for
higher level calls; the result of a recursive call can be returned
directly as the caller's result. This is sometimes called \emph{tail
call optimization} (or ``tail call elimination'' or ``proper tail
calls'').

In converting the backward recursive function \texttt{factorial} to a
tail recursive auxiliary function, we added the parameter \texttt{r} to
\texttt{factIter}. This parameter is sometimes called an
\emph{accumulating parameter} (or just an \emph{accumulator}).

We typically use an accumulating parameter to ``accumulate'' the result
of the computation incrementally for return when the recursion
terminates. In \texttt{factIter}, this ``state'' passed from one
``iteration'' to the next enables us to convert a backward recursive
function to an ``equivalent'' tail recursive one.

Function \texttt{factIter} defines a more general function than
\texttt{factorial}. It computes a factorial when we initialize the
accumulator to 1, but it can compute some multiple of the factorial if
we initialize the accumulator to another value. However, the application
of \texttt{factIter} in \texttt{factorial2} gives the initial value of 1
needed for factorial.

Consider auxiliary function \texttt{fibIter} used by function
\texttt{fib2} below. This function adds two ``accumulating parameters''
to the backward nonlinear recursive function \texttt{fib} to convert the
nonlinear (tree) recursion into a tail recursion. This technique works
for Fibonacci numbers, but the same technique will not work in all
cases.

\begin{verbatim}
    def fib2(n: Int): Int = {

      def fibIter(a: Int, b: Int, n1: Int): Int = n1 match {
        case 0 => b
        case m => fibIter(a+b,a,m-1)
      }
                    
      if (n >= 0)
        fibIter(1,0,n)
      else
        sys.error("Fibonacci undefined for negative value " + n)
    }
\end{verbatim}

Termination: How do we know that \texttt{fibIter} terminates?

Complexity: Function \texttt{fib2} has a time complexity of
O(\texttt{n}) in contrast to O(\texttt{fib(n)}) for \texttt{fib}. This
algorithmic speedup results from the replacement of the very expensive
operation \texttt{fib(n-1)\ +\ fib(n-2)} at each level in \texttt{fib}
by the inexpensive operation \texttt{a\ +\ b} (i.e., addition of two
numbers) in \texttt{fib2}. Because tail call optimization converts the
\texttt{fibIter} recursion to a loop, the space complexity of
\texttt{fib2} is O(1).

\subsection{Logarithmic Recursive
Algorithms}\label{logarithmic-recursive-algorithms}

The backward recursive exponentiation function \texttt{expt1} below
raises a number to a nonnegative integer power. It has time complexity
O(\texttt{n}) and space complexity O(\texttt{n}).

\begin{verbatim}
    def expt1(b: Double, n: Int): Double = n match {
      case 0          => 1
      case m if m > 0 => b * expt1(b,m-1)
      case _          =>
        sys.error("Cannot raise to a negative power " + n)
    }
\end{verbatim}

Termination: How do we know that \texttt{expt1} terminates?

Consider the tail recursive function \texttt{exptIter} called within
function \texttt{expt2} below. This function has time complexity
O(\texttt{n}) and space complexity O(1), assuming tail call
optimization.

\begin{verbatim}
    def expt2(b: Double, n: Int): Double = {

      def exptIter(b1: Double, n1: Int, p: Double): Double = n1 match {
        case 0 => p
        case m => exptIter(b1,m-1,b1*p)
      }

      if (n >= 0)
        exptIter(b,n,1)
      else
        sys.error("Cannot raise to negative power " + n )
    }
\end{verbatim}

Termination: How do we know that \texttt{exptIter} terminates?

The exponentiation function can be made computationally more efficient
by squaring the intermediate values instead of iteratively multiplying.
We observe that:

\begin{verbatim}
    b^n = b^(n/2)^2   if n is even
    b^n = b * b^(n-1) if n is odd
\end{verbatim}

Function \texttt{expt3} below incorporates this observation in an
improved algorithm. Its time complexity is O(\texttt{log(n)}) and space
complexity is O(\texttt{log(n)}).

\begin{verbatim}
    def expt3(b: Double, n: Int): Double = {

      def exptIter(b1: Double, n1: Int): Double = n1 match {
        case 0                 => 1
        case m if (m % 2 == 0) => // i.e. even
            val exp = exptIter(b1, m/2)
            exp * exp                   // backward recursion
        case m                 => // i.e. odd
            b1 * exptIter(b1,m-1)   // backward recursion
      }

      if (n >= 0)
        exptIter(b,n)
      else
        sys.error("Cannot raise to negative power " + n )
    }
\end{verbatim}

Termination: How do we know that \texttt{exptIter} terminates?

\end{document}