Chapter 6

Computability
Recursion
• Sometimes, the best way to solve a problem is by solving a
smaller version of the exact same problem first
• Recursion is a technique that solves a problem by solving a
smaller problem of the same type.

Requirements for Recursive Solution

• At least one “small” case that you can solve directly
• A way of breaking a larger problem down into:
One or more smaller sub-problems
Each of the same kind as the
original
• A way of combining sub-problem results
intoan overall solution to the larger problem
 Recursion…..cont..
Recursive procedures are functions that invoke themselves either
directly (call themselves from within themselves) or
indirectly (calls another method that calls original
method.)
Recursion:
. An alternative to iteration
. Recursion can be very elegant at times,
. Not inexpensive to implement...
Classic examples of recursion
. Calculation of a string length, factorials, divide and conquer,
towers of Hanoi, binary searches, and more
Recursive functions are used in many applied areas.
. In artificial intelligence.
. In searching data structures that are themselves
"recursive" in nature, such as
trees. Concepts and implementation of recursive
functions is an important topic.
 Problems defined recursively
There are many problems whose solution can be defined
recursively.
Example: n factorial

1 if n = 0
n!= (recursive solution)
(n-1)!*n if n > 0

1 if n = 0
n!= (closed form solution)
1*2*3*…*(n- if n >
1)*n 0
 Coding the factorial function

Recursive implementation Iterative implementation

int Factorial(int n) int Factorial(int n)
{
{ int fact = 1;
if (n==0) // base for(int count = 2; count <=
case return 1; n;
else count++)
fact = fact * count;
return n *
Factorial(n-1); return fact;
//Recursive case }
}
 Exampl
e
n choose k (combinations)
Given n things, how many different sets of size k
can be chosen?

kn = n-1 + k-1n- , 1 < k < n (recursive solution)

knk1 = n!
k!(n-k)! , 1 < k < n (closed-form
with base cases: solution)
1n = n (k = 1), n = 1 (k =
n)
 n choose k (combinations)

int Combinations(int n, int k)

{
if(k == 1) // base
case 1 return n;
else if (n == k) // base case 2
return 1;
else
return(Combinations(n-1, k)
+ Combinations(n-1, k-1));
}
 Recursion vs. iteration

• Iteration can be used in place of recursion

• An iterative algorithm uses a looping construct
• A recursive algorithm uses a branching structure

• Recursive solutions are often less efficient, in terms

of both time and space, than iterative solutions
• Recursion can simplify the solution of a problem,
often resulting in shorter, more easily understood source
code
 Towers of Hanoi

• Move stack of disks from one peg to another

• Move one disk at a time
• Larger disk may never be on top of smaller disk
 The Expense of Recursive Functions
. Recursion => has a significant overhead…
. "Deeper" we go => need additional copies of the
data
.. not always small number of data
items.
. These ‘copies’ are stored in "stack frames“ which
contain
Current values and outstanding function calls, and more
. Each "call" results in a stack frame.
Each requires space, allocation of space, and processing
time.
Note:.. Recursive functions – not efficient from a
system
resource perspective.
.. Can pay dividends in:
... ease of writing and maintaining as compared to
 General Recursive Design Strategy
• Identify the base case(s) (for direct solution)
• Devise a problem splitting strategy
• Subproblems must be smaller
• Subproblems must work towards a base case
• Devise a solution combining strategy
Procedure:
1. Find a "Base Case " (That is what we shoot for.)
2. Develop the Recursive Case:
Base Case was sum(1).
We know the answer to this one!
we will always have a simple *normally’ assignment statement
here, such as assigning a value of null or 0 or 1. You will see.
Recursive Case was sum (n-1) which will (must) eventually lead
to sum(1)
Your general recursive case must progress to the base case.
An absolute MUST to conclude the method calls.
 Base Case
"Base case"
a very important notion!
 A base case is one that is simple;
 one that we are working ‘down’ toward
working "down" toward, since, as it turns out, we normally go
"down" or “decrease” some value or some quantity (such
as length of a string) toward the base case. (e.g.
We know the length of an empty string is 0; we know that
0! And 1! By definition = 1…)

 Determining the base case ensures the recursive

function will terminate someday!!
 Writing Recursive Programs.

Have spoken about the "base case" and "recursive

case."

.. base case,
Difficulty and (Some
in writing books
recursive calls this:
routines "trivial case“)
is identifying
.. Recursive ( Some books calls this: "complex case")
case.
Base case
A case that is not recursive and directly obtainable.
Will have a value of 1 or 0 or null or
something having some kind of discrete
value…

Recursive case
A case that is ultimately defined in terms of base case.
 Stated equivalently:

Complex case
. Must be defined in terms of a "simpler" case
. Plus the base case must be:
. a directly solvable, non-
recursive trivial case
We develop solutions using the assumption that the
simpler
case has already been solved.
 SIMULATING RECURSION

 Some languages do not support recursion.

 It is often very common to be able to come up with a
recursive solutions to a problem.
 Since some compilers do not support recursion, we need to be able to
come up with non-recursive solutions. (Iterative Routines)

 Recursive solutions are often more expensive than non-

recursive solutions in Time and space.
 Heavy use of recursive solutions for production systems may dictate
non-recursive solutions to problems.
 Let's look at iterative solutions first.
 In Practice: Conflicts

There are conflicts between

• machine efficiency and
• programmer efficiency
• It is more efficient for the machine to lose some efficiency than
a high-cost programmer.
• It may not be worth the effort to construct a non-
recursive
solution for a problem solved naturally recursively.
Recursively
Enumerable and
Recursive Languages
Definition:

A language is recursively enumerable: if some Turing

machine accepts it.
Let L be a recursively enumerable
language and M the Turing Machine t hat
accepts it

If w ∈ L then M: halts in a final state.

For string w :

If w ∉ L then M : halts in a non-final state or

loops forever
Definition:
• A language is recursive: if some machine
Turing accepts it and halts on any input
string
• In other words: A language is recursive if there
is a membership algorithm for it.

• Let L be a recursive language and M the

Turing Machine that accepts it.
For string w:
• If w ∈L then M
• If w ∉ L then M
halts in a final state
halts in a non-final state
 TM Block Diagrams:
• If L is a recursive language, then a TM M that accepts L and always
halts can be pictorially represented by a “chip” or “box” that has
one input and two outputs.
yes
w M
no

• If L is a recursively enumerable language, then a TM M

that accepts L can be pictorially represented by a “box” that
output.
has one yes
w M

Conceivably, M could be provided with an output for “no,” but this

output cannot be counted on. Consequently, we simply ignore it.
Theorem 1: The recursive languages are closed with respect
to complementation, i.e., if L is a recursive language, then so is
L   * L
Proof: Let M be a TM such that L = L(M) and M always
halts.
Construct TM M’ as follows:
M’
yes
yes
w M no
no

Note That:
M’ accepts iff M does not, M’ always halts since M always halts

From this it follows that the complement of L is recursive.

Question: How is the construction achieved? Do we simply complement the
final states in the TM? No! A string in L could end up in the complement of
L. Suppose q5 is an accepting state in M, but q0 is not.
If we simply complemented the final and non-final states, then q0 would be
an
accepting state in M’ but q would not.
Theorem 2: The recursive languages are closed with respect to union,
i.e., if L1 and L2 are recursive languages, then so is
L 3  L1  L 2
Proof: Let M1 and M2 be TMs such that L1 = L(M1) and L2 = L(M2) and
M1 and M2 always halts. Construct TM M’ as follows:
M’ yes
yes start
w M1 M2 no
no

Note That: 
L(M’) = L(M1) L(M2)
L(M’) is a subset of L(M1) U L(M2)
L(M1) U L(M2) is a subset of
L(M’)
M’ always halts since M1 and M2
It follows
always halt from this tLh3at L 1  is recursive.
L
• Theorem 3: The recursive enumerable languages are closed with
respect to union, i.e., if L1 and L2 are recursively enumerable
languages, then so is L 3  L 1  L 2

• Proof: Let M1 and M2 be TMs such that L1 = L(M1) and L2 = L(M2).

Construct M’ as follows:

M’ yes yes
M1

w
yes
M2

Note That:
L(M’) = L(M1) U L(M2)
L(M’) is a subset of L(M1 ) L(M2)
L  L 
L(M1) U L(M2) is a subset of
U 2

M’ halts and1 accepts iff M1 or ML2 halts and

3L(M’)

accepts
• Suppose, M1 and M2 had outputs for “no” in the
previous construction, and these were transferred to the “no”
output for M’
M’ yes yes
M1
no
w
yes
M2 no
no

Question: What would happen if w is in L(M1) but not in L(M2)?

Answer: You could get two outputs – one “yes” and one “no.”
At least M1 will halt and answer accept, M2 may or may not halt.
As before, for the sake of convenience the “no” output
will be ignored.
Theorem 4: If L and L are both recursively enumerable then
L (and therefore L ) is recursive.

Proof: Let M1 and M2 be TMs such that L = L(M1) and

L = L(M2).
Construct M’ as follows:
M’ yes yes
M1

w
yes
M2 no

Note That:
L(M’) = L
L(M’) is a subset of L
L is a subset of
L(M’)
M’ is TM for L
M’ always halts since
either M1 or M2 halts
for any given string
 There is a specific language which is not recursively
enumerable (not accepted by any Turing
Machine)
also there is,and
a specific language which is recursively
enumerable but not recursive