recursion

Concept

Functions that calls itself

• gives rise to iterative and recursive processes
• consists:
  • base case
  • wish
  • bridge

function factorial(n) {
	return n === 1
	? 1 // Base case
	: n         * factorial(n - 1);
	// Bridge   // Wish
}

Deferred operation

• when the right operand needs to be evaluated before the operation can be evaluated
• so the left operand needs to be stored until the right is ready

Recursive processes

• accumulation of defered operations that grows proportionately to the size of the input
• recursive factorial:

function factorial(n) {
	return n === 1
	? 1
	: n * factorial(n - 1);
}

• creates deferred operations, right operand is its recursive function call
• operations build up due to the substitution model

factorial(4)
4 * factorial(3)
4 * (3 * factorial(2))
4 * (3 * (2 * factorial(1))) // longest chain of deferred opeations, 3
4 * (3 * (2 * 1))
4 * (3 * 2)
4 * 6
24

• time and space
• num of steps and max num of deferred operations grow linearly with n

Iterative processes

• no build up of deferred operations
• iterative factorial:

function factorial(n) {
	return iter(1, 1, n);
}
function iter(product, counter, n) {
	return counter > n
	? product
	: iter(counter * product,
		   counter + 1,
		   n);
}

• no operations performed on its own function call

factorial(4)
iter(1, 1, 4) // no deferred operations are created
iter(1, 2, 4)
iter(2, 3, 4)
iter(6, 4, 4)
iter(24, 5, 4)
24

• time but /constant space,
• since there are no deferred operations

Application

Fibonacci series(iterative > recursive solution)

1. Recursive solution

function fib(n) {
	return n <= 1
	? n
	: fib(n - 1) + fib(n - 2); // sum of previous 2 values
}

time grows exponentially, proportionately with the size of the tree

Tree for fib(n) has F(n+1) leaves, where:

2. Iterative solution

function fib(n) {
	return fib_iter(1, 0, n);
}
function fib_iter(a, b, count) {
	// adding up the smaller values on the fib tree count times
	return count === 0
	? b
	: fib_iter(a + b, a, count - 1);
}

time, without “branching”