Recursion

Recursion

A function is defined recursively if it has the following two parts

• An anchor or base cause
  the function is defined for one or more specific values of the parameters
• An inductive or recursive case
  the function's value for current parameter(s) is defined in terms of previously defined function values and/or parameter(s)

Calculating power

double pwr(double val, int n)
{
	if (n == 0)
		return 1;
	if (n == 1)
		return val;
	
	return val * pwr(val, n - 1);
}

Fibonacci

int fib(int n)
{
	if (n <= 1)
		return 1;
		
	return (fib(n-1) + fib(n-2))
}

Tower of Hanoi

void towerOfHanoi(int n, char from, char to, char aux)
{
	if (n == 0)
		return;
	towerOfHanoi(n - 1, from, aux, to);
	cout << "Move" << n << "from" << from << "to" << to << endl;
	towerOfHanoi(n - 1, aux, to, from);
}

int main()
{
	int N = 3;
	towerOfHanoi(N, 'A', 'B', 'C');
}

Recursive definitions

Recursive function implementing the factorial function

int fact(int num)
{
	if (num == 0)
		return 1;
	return num * fact(num - 1);
}

This is incorrect because we don't check the domain of the input parameter. What if the num = -2? Then we created an infinite loop.
To make it work, we can:

• check the parameter value inside the function and return errval (-1) or exception
• make the parameter unsigned int - doesn't allow negative numbers

Converting a number from dec to bin

void decToBin(int num, int base)
{
	if (num > 0)
	{
		decToBin(num / base, base);
		cout << num % base;
	}
}

Recursion or iteration?

Dependent upon nature of the solution and efficiency

Efficiency

Overhead of recursive function - execution time and memory usage
given speed of memory in contemporary computers, we can depend more on how programmer envisions solution
Use of programmer's time
Any program that can be written recursively can also be written iteratively

Recursion and backtracking - 8 Queens puzzle

Place 8 queens on a chessboard
no two queens can attack each other

n-queens puzzle

we put one queen down
check what other positions are free
put next queen on one of the free positions
if there are no places to place the remaining queens, we have to backtrack and check other possibilities

In backtracking, the solution is represented as n-tuple $(x_1,x_2,x_3,\dots ,x_n)$, where $x_i$ is an integer such that $1\le x_i\le n$
$x_i$ specifies column number, where to place the queen in the $i$th row

for (int j = 0; j < k; j++)
	if ((queensInRow[j] == i) // there is already queen in column i
	|| abs(queensInRow[j] - i) == abs(j - k)) // queen on diagonal
		return false;
return true;

Recursive deletion

after deleting pointer, all of its nodes are copied to the first available (with enough free leafs) inorder node
A
/
B C
/ /
D E F
/ /
G H I
If we delete node E, G gets moved to being a leaf of C
If we delete node F, H and I become leafs of G

Height-balanced tree

AVL tree
Resulting binary search is nearly balanced
Perfectly balanced binary tree
Heights of left and right subtrees of root are equal, perfectly balanced binary trees