dsac::recursion Namespace Reference

Code from the chapter "Recursion". More...

Functions
void	reverse_array (int data[], int low, int high)
void	reverse_iterative (int data[], int n)
int	linear_sum (int data[], int n)
int	binary_sum (int data[], int low, int high)
bool	binary_search (int data[], int target, int low, int high)
bool	binary_search (int data[], int n, int target)
bool	binary_search_iterative (int data[], int n, int target)
long	factorial (int n)
	Computes the factorial of the given (nonnegative) integer)
long	fibonacci_bad (int n)
	Returns the nth Fibonacci number (inefficiently).
std::pair< long, long >	fibonacci_good (int n)
	Returns the pair of Fibonacci numbers, F(n) and F(n-1).
long	fibonacci (int n)
	Don't call this (infinite) version.
double	power_slow (double x, int n)
	Computes the value of x raised to the nth power, for nonnegative integer n.
double	power (double x, int n)
	Computes the value of x raised to the nth power, for nonnegative integer n.
void	draw_line (int tickLength, int tickLabel=-1)
	Draws a line with the given tick length, followed by an optional label.
void	draw_interval (int centralLength)
	Draws a ruler interval around a central tick length.
void	draw_ruler (int nInches, int majorLength)
bool	is_unique3 (int data[], int low, int high)

Detailed Description

Code from the chapter "Recursion".

Function Documentation

binary_search() [1/2]

bool dsac::recursion::binary_search	(	int	data[],
		int	n,
		int	target
	)

Returns true if the target value is found in the array of length n.

Parameters

data	sorted array of integers
n	length of data
target	the query value

Returns

true if the target is found, false otherwise

Here is the call graph for this function:

binary_search() [2/2]

bool dsac::recursion::binary_search	(	int	data[],
		int	target,
		int	low,
		int	high
	)

Returns true if the target value is found in the indicated portion of the data array. This search only considers the array portion from data[low] to data[high] inclusive.

Parameters

data	sorted array of integers
target	the query value
low	the index of the left end of the search range
high	the index of the right end of the search range

Returns

true if the target is found, false otherwise

Here is the call graph for this function:

binary_search_iterative()

bool dsac::recursion::binary_search_iterative	(	int	data[],
		int	n,
		int	target
	)

Returns true if the target value is found in the array of length n.

Parameters

data	sorted array of integers
n	length of data
target	the query value

Returns

true if the target is found, false otherwise

binary_sum()

int dsac::recursion::binary_sum	(	int	data[],
		int	low,
		int	high
	)

Returns the sum of subarray data[low] through data[high] inclusive.

Parameters

data	array of integers
low	the index of the first integer in the range
high	the index of the second integer in the range

Returns

the sum of the integers from data[low] through data[high] inclusive

Here is the call graph for this function:

draw_interval()

void dsac::recursion::draw_interval

(

int

centralLength

)

Draws a ruler interval around a central tick length.

Here is the call graph for this function:

draw_line()

void dsac::recursion::draw_line	(	int	tickLength,
		int	tickLabel = -1
	)

Draws a line with the given tick length, followed by an optional label.

draw_ruler()

void dsac::recursion::draw_ruler	(	int	nInches,
		int	majorLength
	)

Draws an English ruler. The level of division depends upon the designated length of the major tick. For example, a major tick of length 3 will produce a ruler with ticks (of length 2) at the half-inch mark and ticks (of length 1) at the quarter-inch marks.

Parameters

nInches	the total number of inches to be drawn
majorLength	the number of dashes used at complete inch marks

Here is the call graph for this function:

factorial()

long dsac::recursion::factorial

(

int

n

)

Computes the factorial of the given (nonnegative) integer)

Here is the call graph for this function:

fibonacci()

long dsac::recursion::fibonacci

(

int

n

)

Don't call this (infinite) version.

Here is the call graph for this function:

fibonacci_bad()

long dsac::recursion::fibonacci_bad

(

int

n

)

Returns the nth Fibonacci number (inefficiently).

Here is the call graph for this function:

fibonacci_good()

std::pair< long, long > dsac::recursion::fibonacci_good

(

int

n

)

Returns the pair of Fibonacci numbers, F(n) and F(n-1).

Here is the call graph for this function:

is_unique3()

bool dsac::recursion::is_unique3	(	int	data[],
		int	low,
		int	high
	)

Returns true if there are no duplicate values from data[low] through data[high].

Parameters

data	array of integers
low	lowest index of interest
high	highest index of interest

Here is the call graph for this function:

linear_sum()

int dsac::recursion::linear_sum	(	int	data[],
		int	n
	)

Returns the sum of the first n integers of the given array.

Parameters

data	array of integers
n	how many integers from the beginning of the array to sum

Returns

the sum of the first n integers of data

Here is the call graph for this function:

power()

double dsac::recursion::power	(	double	x,
		int	n
	)

Computes the value of x raised to the nth power, for nonnegative integer n.

Here is the call graph for this function:

power_slow()

double dsac::recursion::power_slow	(	double	x,
		int	n
	)

Computes the value of x raised to the nth power, for nonnegative integer n.

Here is the call graph for this function:

reverse_array()

void dsac::recursion::reverse_array	(	int	data[],
		int	low,
		int	high
	)

Reverses the contents of subarray data[low] through data[high] inclusive.

Parameters

data	an array of integers
low	the index of the first element in the range to be reversed
high	the index of the last element in the range to be reversed

Here is the call graph for this function:

reverse_iterative()

void dsac::recursion::reverse_iterative	(	int	data[],
		int	n
	)

Reverses the contents of the given array.

Parameters

data	an array of integers
n	length of the array