Examples of Recursive
Functions
Sum the
first size elements of
an array a[]. i.e. Sum = a[0]+a[1]+...+a[size-1]
Sum( a, size ) = Sum( a, size-1 ) + a[size-1], if size
>= 1
Sum( a, 0 )
= 0
int Sum( /* in */ int a[], /* in */ size )
{
if ( size
== 0 )
return
0;
else
return
Sum( a, size-1 ) + a[size-1];
}
==========
Determine
if a string is a palindrome, i.e. reads the same way either left-to-right as
right-to-left e.g. "raw war"
A string str[] is a palindrome if the string str[] from index 0 to index strlen(str)-1 is a palindrome.
A string str[] from index left to index right is a palindrome if the string str[] from index left+1 to index right-1 is a palindrome and str[left]
== str[right], if left <
right.
A string str[] from index left to index right is a palindrome if left == right (i.e. the string has only one
character.)
We will
define a string str[] from index left to index right to be a palindrome if left
> right (i.e. the
string is empty.)
bool IsPalindrome( /* in */ char str[] )
{
return
IsPalindrome( str, 0, strlen(str)-1 );
}
bool IsPalindrome( /* in */ char str[], /* in */ int
left, /* in */ int right )
{
if ( left
>= right )
return
true;
else
{
if (
str[left] != str[right] )
return false;
else
return IsPalindrome( str, left+1, right-1 );
}
}
==========
Reverse the
characters in a string. (Version #1)
Reverse a
string str[] = Reverse
a string str[] from index
0 to index strlen(str)-1.
Reverse a
string str[] from index
left to index right = Swap str[left] and str[right] and reverse string str[] from index left+1 to index right-1, if left < right.
If left >=
right a string str[] is the reverse of itself.
E.g. ReverseString( "abcdef" ) =
ReverseString( "abcdef", 0, 5 )
= ReverseString(
"fbcdea", 1, 4 )
= ReverseString( "fecdba",
2, 3 )
= ReverseString( "fedcba",
3, 2 )
= "fedcba"
void ReverseString( /* in out */ char str[] )
{
ReverseString( str, 0, strlen(str)-1 );
}
void ReverseStrng( /* in out */ char str[], /* in */
int left, /* in */ int right )
{
if ( left
< right )
{
char
swap = str[left];
str[left] = str[right];
str[right]
= swap;
ReverseString( str, left+1, right-1 );
}
}
==========
Reverse the
characters in a string. (Version #2)
Reverse a
string str[] = Reverse
a string str[] from index
0 to the end of
the string.
Reverse a
string str[] from index
left to the end
of the string = Rotate the string from index left to the end of the string 1
character position to the left, and reverse a string str[] from index left+1 to the end of the string, if left <
strlen(str)-1
If left >=
strlen(str)-1 a string str[] is the reverse of itself.
E.g. ReverseString( "abcdef" ) =
ReverseString( "abcdef", 0 )
= ReverseString( "fabcde",
1 )
= ReverseString( "feabcd",
2 )
= ReverseString( "fedabc",
3 )
= ReverseString( "fedcab",
4 )
= ReverseString( "fedcba",
5 )
= "fedcba"
void ReverseString( /* in out */ char str[] )
{
ReverseString(
str, 0, strlen(str)-1 );
}
void ReverseStrng( /* in out */ char str[], /* in */
int left )
{
int right =
strlen(str)-1;
if ( left
< right )
{
char
swap = str[right];
for (
int i = right; i > left; i++ )
str[i] = str[i-1];
str[left] = swap
ReverseString( str, left+1 );
}
}
==========
Reverse the
characters in a string. (Version #3)
E.g. ReverseString( "abcdef" ) =
ReverseString( "abcdef", "" )
= ReverseString( "abcde",
"f" )
= ReverseString( "abcd",
"fe" )
= ReverseString( "abc",
"fed" )
= ReverseString( "ab",
"fedc" )
= ReverseString( "a",
"fedcb" )
= "fedcba"
const char EOS = '\0';
void ReverseString( /* in out */ char str[] )
{
char*
revstr = new char[ strlen(str)+1 ];
revstr[0] =
EOS;
ReverseString( str, revstr );
strcpy(
str, revstr );
delete[]
revstr;
}
void ReverseString( /* in */ char str[], /* in out*/
char revstr[] )
{
int
lengthStr = strlen(str);
if (
lengthStr > 0 )
{
int
lengthRevstr = strlen(revstr);
revstr[
lengthRevstr ] = str[ lengthStr-1 ];
revstr[
lengthRevstr+1 ] = EOS;
str[
lengthStr-1 ] = EOS;
ReverseString( str, revstr );
}
}
==========
Print out
the item values from a linear linked list.
class List
{
public:
...
void
PrintList( ) const;
private:
struct Node
{
int item;
Node*
next;
};
Node*
front;
void
PrintList( /* in */ Node* prt ) const;
};
void List::PrintList( ) const
{
PrintList(
front );
}
void List::PrintList( /* in */ Node* prt ) const
{
if ( ptr !=
NULL )
{
cout
<< ptr->item;
PrintList( ptr->next );
}
}
=========
Print out
the item values from a linear linked list in
reverse order.
class List
{
public:
...
void ReversePrintList(
) const;
private:
struct Node
{
int item;
Node*
next;
};
Node*
front;
void
ReversePrintList( /* in */ Node* prt ) const;
};
void List:: ReversePrintList ( ) const
{
ReversePrintList ( front );
}
void List:: ReversePrintList ( /* in */ Node* prt )
const
{
if ( ptr !=
NULL )
{
ReversePrintList ( ptr->next );
cout << ptr->item;
}
}
=========
Code the
binary search using a recursive function.
bool BinarySearch( /* in */ int vec[], /* in */ int
size, /* in */ int key )
{
return
BinarySearch(
vec,
0, // index of 1st element
size-1, // index of last
element
key );
}
bool BinarySearch(
/* in */
int vec[],
/* in */
int first,
/* in */
int last,
/* in */
int key )
{
if ( first
> last )
return
false;
int
midpoint = ( first + last ) / 2;
if ( key ==
vec[midpoint] )
return
true;
if ( key
< vec[midpoint] )
return BinarySearch(
vec, first, midpoint-1, key );
else // if
( key > vec[midpoint] )
return
BinarySearch( vec, midpoint+1, last, key );
}