Part 11 – Recursive Functions

Recursive function - one whose definition includes one or more

calls to itself
Recursion is applicable when a problem can be reduced repeatedly
to smaller and smaller versions of itself, until a case is reached
that can be directly solved.
Code that performs repetition without recursion (by looping) is
known as iterative code.
Main disadvantage of recursion - can be a very inefficient use of
resources.
Main advantage of recursion - can provide an easier solution
approach to some problems than iteration.

Writing and Tracing a Recursive Function

Terminal Case
To use recursion, reduce a problem repeatedly to simpler versions
of itself until a terminal case is reached (a case simple enough to
be solved directly).
After a terminal case is solved, a solution to the original problem is
put together working backwards.
Example: Finding a factorial. Use idea that n! = n(n-1)!
See factor1.cpp - implements a recursive definition of a factorial
function.
// factorl.cpp
#include<iostream>
using namespace std;

long fact(long n);

int main()
{
long n;
cout << "Enter n>=0: ";
cin >> n;
cout << n << "! = "
<< fact(n) << endl;
return 0;
}

long fact(long n)
{
if(n==0) // terminal case
 return 1;
else // solve a "smaller" case
return n * fact(n-1);
}

Strategy for writing a recursive function:

A common form for the body of a recursive function is:
if (a terminal case)
Give a direct solution for this case.
else
Give a solution to the original problem by
using a call (or calls) to the recursive
function to solve a "smaller" problem (or
problems).
Tracing
A trace of a recursion function call can be complicated. Remember
these important points:
1. None of the recursive calls can be completed until a recursive call
for a terminal case has been reached.
2. Once a terminal case has been reached, then earlier recursive
calls are completed in reverse order in which they were called
because control always returns to the point from which a call was
made.
See windup.cpp - does not do anything useful, but demonstrates
how recursive calls are stacked and then unstacked.
// windup.cpp
#include<iostream>
using namespace std;

void rec_task(int n);

int main()
{
rec_task(4);
return 0;
}

void rec_task(int n)
{
if(n==1) // terminal case
cout << n << " GO BACK" << endl;
else
{
cout << n << " hi\n";
rec_task(n-1);
 cout << n << " bye\n";
}
}
Here is a trace of a call rec_task(4):
rec_task(4): Output "4 hi"; call rec_task(3)
rec_task(3): Output "3 hi"; call rec_task(2)
rec_task(2): Output "2 hi"; call rec_task(1)
rec_task(1): Output "1 GO BACK" - done!
finish rec_task(2): Output "2 bye" - done!
finish rec_task(3): Output "3 bye" - done!
finish rec_task(4): Output "4 bye" - done!

Warning - be aware of the possibility of infinite recursion when you

are writing recursive functions.
Note: You should understand how to trace a call to a recursive
function.

Guidelines for Writing Recursive Functions

Identify the Reductive Step(s) - Solving a problem with
recursion involves subdividing it into subtasks such that at least
one of the subtasks is a "smaller" or easier version of the
original problem. You will use a recursive call to accomplish the
"smaller" version of the problem; you write the code for the
other subtasks.
Identify the Terminal Case(s) - The successive reductions must
eventually lead to a terminal case - these cases usually
correspond to versions of the problem that are so small that
they are very easy to solve. Possible problems: 1) never
reaching a terminal case (infinite recursion) and 2) a reductive
step that does not work properly for all input, usually for values
that are close to a terminal value.
Use Sample Input and Pseudocode - Solve for a specific input
value case, expressing solution using pseudocode.
Example - Outputting Spaces Between the Digits of an Integer
Write a recursive function, print_spaced, that outputs the digits
of an integer in order, with spaces between digits (e.g., 4567
would be printed 4 5 6 7). Note: The digit easiest to extract is
the one's digit - it is the last digit to be displayed. Solve with
recursion.
Use sample input 4567 - subdivide the solution into these steps:
1. Print 4 5 6 (recursive step)
2. Print a space, then print 7 (after step 1 is done)
Use sample input 8 - the solution has just one step:
1. Since 8 is a one digit number (i.e., n<10), print 8
Pseudocode for print_spaced: Let n be the input number
if n<10 (terminal case)
display n
else (recursive step and additional action)
print_spaced (n/10)
display " " and n%10
See spaces.cpp
// spaces.cpp
// output an integer with spaces between digits
#include <iostream>

using namespace std;

void print_spaced (int n);

int main()
{
int m = 123456;
print_spaced (m);
cout << endl;
print_spaced (908070605);
cout << endl;
return 0;
}

void print_spaced (int n)

{
if (n < 10) // terminal case
cout << n;
else // n > 9 -- recursive step
{
print_spaced (n/10);
cout << ' ' << n%10;
}
 }

Example - Printing Numbers with Commas - See commas.cpp

Write a recursive function, print_commas, to print an integer
with commas. For example, the integer 12345008 will be
displayed 12,345,008.
Use sample input 12345008 - solution steps:
1. Print 12,345 (recursive step)
2. Print ,008 (after step 1 is done)
Use sample input 576 – the solution has just one step:
3. Since 576<1000, print 576 (no commas needed)
Pseudocode for print_commas: Let n be the input number
if n<1000 (terminal case)
display n
else (recursive step and additional action)
print_commas(n/1000)
if (n%1000)<10
display ",00" and n%1000
else if (n%1000)<100
display ",0" and n%1000
else
display "," and n%1000
See commas.cpp
// commas.cpp
// output an integer with commas
#include <iostream>

using namespace std;

void print_commas (int n);

int main()
{
int m = 123456;
print_commas(m);
cout << endl;
print_commas(387);
cout << endl;
print_commas(908070605);
cout << endl;
return 0;
}
 void print_commas(int n)
{
if (n < 1000) // terminal case
cout << n;
else // n >=1000 -- recursive step
{
print_commas(n/1000);
if ((n%1000)<10)
cout << ",00" << n%1000;
else if ((n%1000)<100)
cout << ",0" << n%1000;
else
cout << "," << n%1000;
}
}

Recursion and Arrays or Vectors

Example: Recursive Binary Search - Write a recursive procedure
bin_search to search an ordered vector of strings for a string
value and return the index of the element, if found, or return -1 if not
found.
Binary Search Algorithm:
Compare the search value to the middle element of the sorted
search list. If they are equal, the search value has been found. But,
if they are unequal, then determine if the search value is in the lower
or upper half of the search list and search the appropriate half (this
is a recursive step). If the search leads to an “empty” half to search,
conclude that the search value is not in the search list.
Pseudocode for bin_search:
Let first and last be indices of first and last vector index locations
to be searched, and want be the string to be searched for in the
vector, and V be the vector of strings to be searched
mid=(first+last)/2
if(first>last) (terminal case)
return -1
if(want equals V[mid])
return mid
if(want is less than V[mid]) (recursive cases)
return bin_search(V, want, first, mid-1) (search first half of V)
else
return bin_search(V,want,mid+1,last) (search second half of V)
See binsrch.cpp
// binsrch.cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int bin_search(const vector<string>& V,string want,int

first,int last);
// returns position of want in vector V
// returns -1 if not in vector.

void get_vector (vector<string>& V);

int main()
{
vector<string> V;
string want;
int where;
char ans;
get_vector(V);
do {
cout << "Enter string to find: ";
cin >> want;
where = bin_search(V,want,0,V.size()-1);
if (where>=0)
cout << want << " is in cell " << where;
else
cout << want << " is not in the vector.";
cout << "\n\nAgain? (Y/N): "; cin >> ans;
}
while (ans!='n' && ans!='N');
return 0;
}

int bin_search(const vector<string>& V,string want,int

first,int last)
{
int mid;
mid=(first+last)/2;
if(first>last)
return -1;
if(want == V[mid])
return mid;
if(want < V[mid])
return bin_search(V, want, first, mid-1);
else
return bin_search(V,want,mid+1,last);
}

void get_vector (vector<string>& V)

{
 int n;
cout << "How many elements in vector? ";
cin >> n;
cout << "Enter vector elements in ascending order.\n";
V.resize(n);
for(int i=0; i<n; i++)
cin >> V[i];
}

A Very Inefficient Recursive Function

When a body of a recursive function contains more than one
recursive call, it may be possible that redundant recursive calls will
be made. This makes such a function very inefficient.

Example - Write a recursive function, fib, that will determine and

return the nth Fibonacci number.

Fibonacci Numbers: A sequence of numbers such that the first and

second positive Fibonacci numbers are both 1; thereafter, each
Fibonacci number is the sum of the previous two Fibonacci
numbers: 1,1,2,3,5,8,13,21,34,55,89,144,…
This sequence is determined by these three equations:
fib(1) = 1
fib(2) = 1
fib(n) = fib(n-1)+fib(n-2)
See rec_fib.cpp
// rec_fib.cpp
#include <iostream>
using namespace std;
unsigned long fib (int n);
int count; //global variable to count how many fig calls occur
int main()
{
int n;
count = 0;
cout << "Calculate Fibonacci number #: ";
cin >> n;
cout << fib(n) << endl;
cout << count << " calls to fib.\n";
return 0;
}

unsigned long fib (int n)

{
count ++;
if (n==1 || n==2) // terminal cases
 return 1;
else
return fib(n-1) + fib(n-2);
}
Tracing the call fib(5):
fib(5)
fib(4) + fib(3)
fib(3) + fib(2) fib(2) + fib(1)
fib(2) + fib(1) ret 1 ret 1 ret 1
ret 1 ret 1 2
2 + 1 V
3 + 2
5
Note: The call fib(5) generates 1 call to fib(4), 2 calls to fib(3), 3 calls
to fib(2), and 2 calls to fib(1). This is a very inefficient algorithm.
Note that for larger values of n, the inefficiency increases.

A Problem That Is Very Difficult to Solve Iteratively

Towers of Hanoi Problem
 Problem: Assume that you have three pegs, A, B, and C, and a
set of disks, all of different diameters, with holes in them (so that
they can slide onto the pegs). Start with all the disks on a single
peg (say the leftmost, A), in order of size (with the smallest on
top). The object of the problem is to move the pile of disks to a
specified peg (say the rightmost, C), by moving one disk at a time,
under this constraint: A legal move consists of taking the top disk
from any peg and putting it on either of the other two pegs, but a
disk may never be placed on top of a disk that is smaller than
itself.
 Very easy case - suppose there are 2 disks; somewhat easy case
- suppose there are 3 disks; much harder case - suppose there
are 4 disks; how about 5 or 10 disks?
 Seems difficult to develop a general case strategy to solve for n
disks. A natural solution can be found using recursion: Assuming
the 3 disk case was solved, solve the 4 disk case like this:
1. Use 3-disk strategy to move top 3 disks to the middle peg, B.
2. Move 4th disk to the right peg, C.
3. Use 3-disk strategy to move the 3 disks from the middle peg, B,
to the right peg, C.
 So, to generalize to the n disk case, use a solution based on the
assumption that we could figure out a solution to the n-1 disk
case:
1. Use n-1-disk strategy to move the top n-1 disks to the middle
peg, B.
2. Move the nth disk to the right peg, C.
3. Use n-1-disk strategy to move the n-1 disks from the middle
peg, B, to the right peg, C.
See hanoi.cpp - the above recursive algorithm is built into the
function move_pile.
// hanoi.cpp
#include<iostream>
using namespace std;

void move_pile(int n, char src, char dest, char aux);

int main()
{
int n;
cout << "How many disks? ";
cin >> n;
char src = 'A', dest = 'C', aux = 'B';
move_pile(n, src, dest, aux);
cout << endl;
return 0;
}

void move_pile(int n, char src, char dest, char aux)

{
if(n==1)
cout << "Move " << src << " to " << dest << endl;
else
{
move_pile(n-1, src, aux, dest);
cout << "Move " << src << " to " << dest << endl;
move_pile(n-1, aux, dest, src);
}
}