Transcript Final Review

Programming
Final Review
COMP102 Prog. Fundamentals I: Character I/O/ Slide 2
Scope





The scope of an identifier does not apply if the same
identifier is declared in an inner block.
A global declaration of an identifier is made outside the
bodies of all functions, including the main function. It is
normally grouped with the other global declarations and
placed at the beginning of the program file.
A local declaration of an identifier is made inside a block
of code which could be the body of a function.
Globally declared identifiers can be accessed anywhere
in the program.
Locally declared identifiers cannot be accessed outside
of the block they were declared in.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 3
Scope: Example 3

Number in Increment() is the global variable.
#include <iostream>
using namespace std;
int Number; //global variable
void Increment(int IncNum) {
IncNum = IncNum + 3;
cout << IncNum << endl;
Number = Number + 1; }
int main() {
Number = 1;
Increment(Number);
cout << Number << endl;
return 0;
}
Programming
Character I/O
COMP102 Prog. Fundamentals I: Character I/O/ Slide 5
More on char Type

Constant Declaration:
const char star = '*';

Variable Declaration:
char letter;

Variable Assignment:
letter = 'A';

Input/Output:
char t, x, y, z;
cin >> t >> x >> y >> z;
INPUT: 1X3Y
t = '1'; x = 'X'; y = '3'; z = 'Y';
cout << t << x << y << z << endl;
OUTPUT: 1X3Y
COMP102 Prog. Fundamentals I: Character I/O/ Slide 6
Example 1
int main()
{
char character;
cout << "Please enter a character!\n";
cin >> character;
cout << "As int " << (int)(character) << endl ;
cout << "As char " << (char)(character) << endl;
cout << "As bool ";
if ((bool)(character))
cout << "true\n";
else
cout << "false\n";
return 0;
}
COMP102 Prog. Fundamentals I: Character I/O/ Slide 7
Classifications of the character type
characters
control
printable
space
graphical
alphanumeric
alphabetic
upper
lower
digit
punctuation
COMP102 Prog. Fundamentals I: Character I/O/ Slide 8
Some Functions on char from ctype.h
Classifying Functions:

isupper(c) returns nonzero if c is an
uppercase letter.

islower(c) returns nonzero if c is a lowercase
letter.

isdigit(c) returns nonzero if c is a digit
character.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 9
More Functions on char from ctype.h
Classifying Functions:

isalpha(c) returns nonzero if either
islower(c) or isupper(c) returns nonzero.

isalnum(c): returns nonzero if either
isalpha(c) or isdigit(c) returns nonzero.

isspace(c): returns nonzero if c is a space,
newline, formfeed, carriage return,
tab or vertical tab character.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 10
More Functions on char from ctype.h
Conversion Functions:

tolower(c): if c is uppercase, returns
lowercase; otherwise, returns c.

toupper(c): if c is lowercase, returns
uppercase; otherwise, returns c.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 11
Relational Operators and the Type char

'0' through '9' have ASCII code values 48 through 57
'0' < '1' < . . . < '9'

'A' through 'Z' have ASCII code values 65 through 90
'A' < 'B' < . . .< 'Z'

'a' through 'z' have ASCII code values 97 through
122
'a' < 'b' < . . .< 'z'
COMP102 Prog. Fundamentals I: Character I/O/ Slide 12
Reading/Writing One Character at a Time

get(char& character) reads a single
character named character from the input
stream.

put(char character) writes a single
character named character to the output
stream.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 13
Example 4: get(c) and put(c)
#include <iostream>
using namespace std;
int main()
{
char character;
cout << "Please enter some names ";
cout << "(0 to stop) \n";
do{
cin.get(character);
cout.put(character);
}while (character != '0');
return 0;
Programming
File I/O
COMP102 Prog. Fundamentals I: Character I/O/ Slide 15
Input File-Related Functions
#include <fstream>
ifstream fsIn;

fsIn.open("fname.txt")


connects stream fsIn to the external file
"fname.txt ".
fsIn.close()

disconnects the stream and associated file.
fsIn >> c;
 fsIn.eof()


//Behaves just like cin
tests for the end-of-file condition.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 16
Output File-Related Functions
#include <fstream>
ofstream fsOut;

fsOut.open("fname.txt")


fsOut.close()


connects stream fsOut to the external file
"fname.txt".
disconnects the stream and associated file.
fsOut << c;
//Behaves just like cout
COMP102 Prog. Fundamentals I: Character I/O/ Slide 17
Copyright © 2000 by Brooks/Cole Publishing Company
A division of International Thomson Publishing Inc.
File Open Result
COMP102 Prog. Fundamentals I: Character I/O/ Slide 18
File I/O: Example 2
// Reads three numbers from the file input_file.dat,
// sums the numbers, and writes the sum to the file
// output_file.dat.
#include <iostream>
// for cin, cout
#include <fstream>
// for ifstream, ostream
using namespace std;
int main(){
// declare the input and output streams
ifstream input_stream;
ofstream output_stream;
// declare the input and output file names
char input_file_name[16], output_file_name[16];
COMP102 Prog. Fundamentals I: Character I/O/ Slide 19
File I/O: Example 2
// user supplies the input and
// output file names
cout << "input_stream.open(input_file_name)”;
cout << "Enter the input file name "
<< "(maximum 15 characters):\n";
cin >> input_file_name;
cout << "Enter the output file name "
<< "(maximum 15 characters):\n";
cin >> output_file_name;
// open the input file
input_stream.open(input_file_name);
// open the output file
output_stream.open(output_file_name);
COMP102 Prog. Fundamentals I: Character I/O/ Slide 20
File I/O: Example 2
// declare variables and read in the data (3 numbers)
int first, second, third;
input_stream >> first >> second >> third;
// write the data to the output file
output_stream << "The sum of the first 3\n"
<< "numbers in input_file.dat\n"
<< "is " << (first + second + third)
<< endl;
// close the input and output files
input_stream.close();
output_stream.close();
return 0;
}
Programming
Arrays
COMP102 Prog. Fundamentals I: Character I/O/ Slide 22
Array Declaration




Syntax:
<type> <arrayName>[<array_size>]
Ex. int Ar[10];
The array elements are all values of the type <type>.
The size of the array is indicated by <array_size>, the
number of elements in the array.
<array_size> must be an int constant or a constant
expression. Note that an array can have multiple
dimensions.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 23
Array Declaration
// array of 10 uninitialized ints
int Ar[10];
Ar
0
0
1
2
3
4
5
6
7
8
9
--
--
--
--
--
--
--
--
--
--
1
2
3
4
5
COMP102 Prog. Fundamentals I: Character I/O/ Slide 24
Subscripting

Declare an array of 10 integers:
int Ar[10];

// array of 10 ints
To access an individual element we must apply a
subscript to array named Ar.

A subscript is a bracketed expression.
– The expression in the brackets is known as the index.

First element of array has index 0.
Ar[0]

Second element of array has index 1, and so on.
Ar[1], Ar[2], Ar[3],…

Last element has an index one less than the size of the array.
Ar[9]

Incorrect indexing is a common error.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 25
Array Initialization Ex. 4
int Ar[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
0
Ar
9
1
8
2
7
3
6
4
5
5
4
6
3
7
2
8
1
9
0
Ar[3] = -1;
-1
6
0
Ar
9
1
8
2
7
3
-1
4
5
5
4
6
3
7
2
8
1
9
0
COMP102 Prog. Fundamentals I: Character I/O/ Slide 26
Ex. 1: 2-D Array Initialization
It is highly recommended, however, that you nest the data in braces
to show the exact nature of the array. For example, array table is
better initialized as :
// 2-D array of 18 initialized chars
const int NUM_ROWS = 3, NUM_COLS = 6;
Char table[NUM_ROWS][NUM_COLS]={
{’a’,’b’,’c’,’d’,’e’,’f’},
{’g’,’h’,’i’,’j’,’k’,’l’},
{’m’,’n’,’o’,’p’,’q’,’r’}
};
0
1
2
3
4
5
table 0
a
b
c
d
e
f
1
2
g
m
h
n
i
o
j
p
k
q
l
r
COMP102 Prog. Fundamentals I: Character I/O/ Slide 27
Ex. 1: 2-D Array Inputting Values
Another way to fill up the values is to read them from the keyboard. For
a two-dimensional array this usually requires nested for loops. If the
array is an n by m array, the first loop varies the row from 0 to n-1.
The second loop varies the column from 0 to m -1.
const int NUM_ROWS = 3, NUM_COLS = 6;
for (int row=0; row < NUM_ROWS; row++)
for (int column = 0; column < NUM_COLS; column++)
cin.get(table[row][column]);
//input “two-dimensional array”
table
0
1
2
0
1
2
3
4
5
t
m
n
w
e
a
o
n
l
s
d
i
a
i
o
r
COMP102 Prog. Fundamentals I: Character I/O/ Slide 28
Passing Arrays as Parameters




Arrays are always passed by reference.
The “[ ]” in the formal parameter
specification indicates that the variable is
an array.
It is a good practice to pass the dimension
of the array as another parameter.
If the function must not change any
element of the array then const should be
used in the formal parameter specification
of that array.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 29
Passing An Array Example 3
Notice empty brackets
int ListMinimum(const int Ar[], int asize)
{
Could we just
int SmallestValueSoFar = Ar[0];
assign a 0
for (int i = 1; i < asize; ++i) {
and have it
if (Ar[i] < SmallestValueSoFar ) {
work?
SmallestValueSoFar = Ar[i];
}
}
return SmallestValueSoFar ;
}
COMP102 Prog. Fundamentals I: Character I/O/ Slide 30
Example 5
// Add a[i] and b[i] and store the sum in c[i]
void add_array(int size,
// in: array size
double a[],
// in: first array
double b[],
// in: second array
double c[] ) // out: result array
// array elements with subscripts ranging from
// 0 to size-1 are added element by element
// Pre: a[i] and b[i] (0<=i<=size-1) are defined
// Post: c[i] = a[i] + b[i] (0<=i<=size-1)
{
}
int i;
// Add a[i] and b[i] and store result in c[i]
for (i=0; i < size; i++)
c[i] = a[i] + b[i];
Programming
Strings
COMP102 Prog. Fundamentals I: Character I/O/ Slide 32
Character Strings


A sequence of characters is often referred to as a
character “string”.
A string is stored in an array of type char ending with
the null character '\0 '.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 33
Character Strings

A string containing a single character takes up 2
bytes of storage.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 34
getline

The function getline can be used to read an entire line
of input into a string variable.

The getline function has three parameters:

The first specifies the area into which the string is to
be read.

The second specifies the maximum number of
characters, including the string delimiter.

The third specifies an optional terminating character. If
not included, getline stops at ‘\n’.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 35
COMP102 Prog. Fundamentals I: Character I/O/ Slide 36
Ex. 6: String Copy Function
void strcpy(char dest[], const char src[]);
//copies string src into string dest
example:
char name1[16], name2[16];
strcpy(name1,"Chan Tai Man");
name1:
C h a n
T a i
M a n \0 ? ? ?
strcpy(name2,"999999999999999");
name2:
9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 \0
strcpy(name2,name1);
name2:
C
h a n
T a i
M a n \0
9 9 \0
COMP102 Prog. Fundamentals I: Character I/O/ Slide 37
String Comparison
int strcmp(char s1[], char s2[]);
/*compares strings s1 and s2, returns
< 0 if s1 < s2
= 0 if s1 == s2 (i.e. strcmp returns false)
> 0 if s1 > s2
*/
int strncmp(char s1[], char s2[], int limit);
/* Same as strcmp except that at most limit characters are
compared. */
COMP102 Prog. Fundamentals I: Character I/O/ Slide 38
Programming
Structures
COMP102 Prog. Fundamentals I: Character I/O/ Slide 40
Structures

A Structure is a collection of related data items,
possibly of different types.

A structure type in C++ is called struct.

A struct is heterogeneous in that it can be
composed of data of different types.

In contrast, array is homogeneous since it can
contain only data of the same type.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 41
Structures

Individual components of a struct type are
called members (or fields).

Members can be of different types (simple,
array or struct).

A struct is named as a whole while individual
members are named using field identifiers.

Complex data structures can be formed by
defining arrays of structs.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 42
struct basics

Definition of a structure:
struct <struct-type>{
<type> <identifier_list>;
<type> <identifier_list>;
...
} ;

Each identifier
defines a member
of the structure.
Example:
struct Date {
int day;
int month;
int year;
} ;
The “Date” structure
has 3 members,
day, month & year.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 43
struct examples

Example:
struct BankAccount{
char Name[15];
int AcountNo[10];
double balance;
Date Birthday;
};

The “BankAcount”
structure has simple,
array and structure
types as members.
Example:
struct StudentRecord{
char Name[15];
int Id;
char Dept[5];
char Gender;
};
The “StudentRecord”
structure has 4
members.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 44
struct basics

Declaration of a variable of struct type:
<struct-type> <identifier_list>;

Example:
StudentRecord Student1, Student2;
Name
Student1
Id
Dept
Name
Gender
Id
Gender
Student2
Dept
Student1 and Student2 are variables of
StudentRecord type.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 45
Ex. 2: struct-to-struct assignment


The values contained in one struct type
variable can be assigned to another variable
Student1
of the same struct type.
Chan Tai Man
Example:
strcpy(Student1.Name,
"Chan Tai Man");
Student1.Id = 12345;
strcpy(Student1.Dept, "COMP");
Student1.gender = 'M';
Student2 = Student1;
12345
M
COMP
Chan Tai Man
12345
Student2
COMP
M
COMP102 Prog. Fundamentals I: Character I/O/ Slide 46
Ex. 3-5: Nested structures

We can nest structures inside structures.

Examples:
struct point{
double x, y;
};
point P;
(P.x, P.y)
(L.p2.x, L.p2.y)
(L.p1.x, L.p1.y)
struct line{
point p1, p2;
};
line L;
struct triangle{
point p1, p2, p3;
};
triangle T;
(T.p2.x, T.p2.y)
(T.p3.x, T.p3.y)
(T.p1.x, T.p1.y)
COMP102 Prog. Fundamentals I: Character I/O/ Slide 47
Arrays of structures

An ordinary array: One type of data
0

1
2
…
98
99
An array of structs: Multiple types of data in each
array element.
0
1
2
…
98
99
COMP102 Prog. Fundamentals I: Character I/O/ Slide 48
Arrays of structures


We often use arrays of structures.
Example:
StudentRecord Class[100];
strcpy(Class[98].Name, "Chan Tai Man");
Class[98].Id = 12345;
strcpy(Class[98].Dept, "COMP");
Chan Tai Man
Class[98].gender = 'M';
12345
M
Class[0] = Class[98];
COMP
...
0
1
2
…
98
99
COMP102 Prog. Fundamentals I: Character I/O/ Slide 49
Ex. 10: Initialize Data of struct Type
By assignment during declaration;
example:
struct StudentRecord { // student record
double totalgrade;
char name[name_size], id[id_size];
int grade[no_grades];
};
StudentRecord student1 = {
0.0,
"CHAN Tai Man", "12345678",
{80, 67, 34, 67}
};

COMP102 Prog. Fundamentals I: Character I/O/ Slide 50
Ex. 11: Initialize Data of struct Type
Initialization of a “nested” structure:
struct Point {
int x, y;
}; //defines the coordinates of a point
struct Triangle {
Point vertex[3];
double area;
}; //defines a triangle
Triangle tlist[2] = {
{{{0, 0}, {1, 0}, {0, 1}}, 0.5}, // 1st Triangle
{{{2, 0}, {3, 0}, {3, 1}}, 0.5}
};
// 2nd Triangle
COMP102 Prog. Fundamentals I: Character I/O/ Slide 51
Ex. 12: Using struct Type in Functions


As parameters: both pass-by-value and pass-by-reference are supported.
As type of function: assembly of return value needed.
Example:
StudentRecord shrink_wrap(
// a function with
const char sname[],
// name shrink_wrap of
const char sid[],
// type StudentRecord
const int sgrade[])
{
StudentRecord temp;
strcpy (temp.name, sname);
strcpy (temp.id, sid);
for (int index=0; index<no_grades; index++)
temp.grade[index] = sgrade[index];
return temp;
} // Defines an initialization function
Programming
Searching
Arrays
COMP102 Prog. Fundamentals I: Character I/O/ Slide 53
Unordered Linear Search

Search an unordered array of integers for a
value and return its index if the value is found.
Otherwise, return -1.
A[0] A[1] A[2]
14
A[3] A[4] A[5] A[6] A[7]
2 10 5 1 3 17 2
 Algorithm:
Start with the first array element (index 0)
while(more elements in array){
if value found at current index, return index;
Try next element (increment index);
}
Value not found, return -1;
COMP102 Prog. Fundamentals I: Character I/O/ Slide 54
Unordered Linear Search
// Searches an unordered array of integers
int search(int data[], //input: array
int size,
//input: array size
int value){ //input: search value
// output: if found, return index;
//
otherwise, return –1.
for(int index = 0; index < size; index++){
if(data[index] == value)
return index;
}
return -1;
}
COMP102 Prog. Fundamentals I: Character I/O/ Slide 55
Ordered Linear Search

Search an ordered array of integers for a value
and return its index if the value is found;
Otherwise, return -1.
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
1

2
3
5
7 10 14 17
Linear search can stop immediately when it has
passed the possible position of the search value.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 56
Ordered Linear Search
// Searches an ordered array of integers
int lsearch(int data[],// input: array
int size, // input: array size
int value // input: value to find
) {
// output: index if found
for(int index=0; index<size; index++){
if(data[index] > value)
return -1;
else if(data[index] == value)
return index;
}
return -1;
}
COMP102 Prog. Fundamentals I: Character I/O/ Slide 57
Binary Search

Search an ordered array of integers for a value and return
its index if the value is found. Otherwise, return -1.
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
1

2
3
5
7 10 14 17
Binary search skips over parts of the array if the search
value cannot possibly be there.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 58
6
Copyright © 2000 by Brooks/Cole Publishing Company
A division of International Thomson Publishing Inc.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 59
COMP102 Prog. Fundamentals I: Character I/O/ Slide 60
Binary Search

Binary search is based on the “divide-andconquer” strategy which works as follows:
 Start
by looking at the middle element of the
array
– 1. If the value it holds is lower than the search
element, eliminate the first half of the array from
further consideration.
– 2. If the value it holds is higher than the search
element, eliminate the second half of the array from
further consideration.
 Repeat
this process until the element is found,
or until the entire array has been eliminated.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 61
Binary Search
// Searches an ordered array of integers
int bsearch(int data[], // input: array
int size,
// input: array size
int value
// input: value to find
)
// output: if found,return index
{
//
otherwise, return -1
int first, middle, last;
first = 0;
last = size - 1;
while (true) {
middle = (first + last) / 2;
if (data[middle] == value)
return middle;
else if (first >= last)
return -1;
else if (value < data[middle])
last = middle - 1;
else
first = middle + 1;
}
}
Programming
Sorting
Arrays
COMP102 Prog. Fundamentals I: Character I/O/ Slide 63
Ex. 1A: Selection Sort

Selection sort performs sorting by
repeatedly putting the largest element in
the unsorted portion of the array to the end
of this unsorted portion until the whole
array is sorted.

It is similar to the way that many people do
their sorting.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 64
Before sorting
14
2
10
5
1
3
17
7
After pass 1
14
2
10
5
1
3
7
17
After pass 2
7
2
10
5
1
3
14
17
After pass 3
7
2
3
5
1
10
14
17
After pass 4
1
2
3
5
7
10
14
17
// Sort array of integers in ascending order
void select(int data[], // in/output: array
int size){ // input: array size
int temp;
// for swap
int max_index; // index of max value
for (int rightmost=size-1; rightmost>0; rightmost--){
//find the largest item in the unsorted portion
//rightmost is the end point of the unsorted part of array
max_index = 0; //points the largest element
for ( int current=1; current<=rightmost; current++)
if (data[current] > data[max_index])
max_index = current;
//swap the largest item with last item if necessary
if (data[max_index] > data[rightmost]){
temp = data[max_index];
// swap
data[max_index] = data[rightmost];
data[rightmost] = temp;
}
}}
COMP102 Prog. Fundamentals I: Character I/O/ Slide 66
Ex. 1B: Bubble Sort





Bubble sort examines the array from start
to finish, comparing elements as it goes.
Any time it finds a larger element before a smaller
element, it swaps the two.
In this way, the larger elements are passed
towards the end.
The largest element of the array therefore
"bubbles" to the end of the array.
Then it repeats the process for the unsorted
portion of the array until the whole array is sorted.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 67
Ex. 1B: Bubble Sort
 Algorithm
 Define
the entire array as the unsorted
portion of the array.
 While the unsorted portion of the array has
more than one element:
1. For every element in the unsorted portion,
swap with the next neighbor if it is larger than
the neighbor.
2. Reduce the size of the unsorted portion of the
array by 1.
Before sorting
14
2
10
5
1
3
17
7
outer=7, inner=0
2
14
10
5
1
3
17
7
outer=7, inner=1
2
10
14
5
1
3
17
7
outer=7, inner=2
2
10
5
14
1
3
17
7
outer=7, inner=3
2
10
5
1
14
3
17
7
outer=7, inner=4
2
10
5
1
3
14
17
7
outer=7, inner=6
2
10
5
1
3
14
7
17
outer=6, inner=1
2
5
10
1
3
14
7
17
outer=6, inner=2
2
5
1
10
3
14
7
17
outer=6, inner=3
2
5
1
3
10
14
7
17
outer=6, inner=5
2
5
1
3
10
7
14
17
outer=5, inner=1
2
1
5
3
10
7
14
17
outer=5, inner=2
2
1
3
5
10
7
14
17
outer=5, inner=4
2
1
3
5
7
10
14
17
outer=4, inner=0
1
2
3
5
7
10
14
17
1
2
3
5
7
10
14
17
--outer=1, inner=0
//Example1b: Bobble sort
// Sort an array of integers in ascending order
void bubble(int data[],
// in/output: array
int size){
// input: array size
int temp;
// for swap
for(int outer=size-1; outer > 0; outer--){
for (int inner=0; inner < outer; inner++) {
// traverse the nested loops
if ( data[inner] > data[inner+1] ) {
// swap current element with next
// if the current element is greater
temp = data[inner];
data[inner] = data[inner+1];
data[inner+1] = temp;
}
} // inner for loop
} // outer for loop
}
Programming
Recursion
COMP102 Prog. Fundamentals I: Character I/O/ Slide 71
Ex. 2: Recursion
In general, we can express the factorial
function as follows:
n! = n * (n-1)!
Is this correct? Well… almost. The factorial
function is only defined for positive integers.
So we should be a little bit more precise:
n! = 1
n! = n * (n-1)!
(if n is equal to 1)
(if n is larger than 1)
COMP102 Prog. Fundamentals I: Character I/O/ Slide 72
Ex. 2: Recursion
The C++ equivalent of this definition:
int fac(int numb){
if(numb<=1)
return 1;
else
return numb * fac(numb-1);
}
recursion means that a function calls
itself
COMP102 Prog. Fundamentals I: Character I/O/ Slide 73
Recursion
We must always make sure that the recursion
bottoms out:


A recursive function must contain at least one
non-recursive branch.
The recursive calls must eventually lead to a
non-recursive branch.
COMP102 Prog. Fundamentals I: Character I/O/ Slide 74
Recursion General Form

How to write recursively?
int recur_fn(parameters){
if(stopping condition)
return stopping value;
// other stopping conditions if needed
return function of recur_fn(revised parameters)
}
COMP102 Prog. Fundamentals I: Character I/O/ Slide 75
Direct Computation Method

Fibonacci numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
where each number is the sum of the preceding
two.

Recursive definition:



F(0) = 0;
F(1) = 1;
F(number) = F(number-1)+ F(number-2);
COMP102 Prog. Fundamentals I: Character I/O/ Slide 76
Example 3: Fibonacci numbers
//Calculate Fibonacci numbers using recursive function.
int fib(int number)
{
if (number == 0) return 0;
if (number == 1) return 1;
return (fib(number-1) + fib(number-2));
}
int main(){ // driver function
int inp_number;
cout << "Please enter an integer: ";
cin >> inp_number;
cout << "The Fibonacci number for "<< inp_number
<< " is "<< fib(inp_number)<<endl;
return 0;
}