Recursion

Iterative Function

uses a loop to execute the same logic multiple times

Recursive Function

calls itself to execute the same logic multiple times

Are Recursive and Iterable Functions Interchangeable?

yes

Order of Execution

depends on whether the logic is before or after the self-call

//logic before recursion
void counter(int n) {
	if (n != 0) {
		print("loop " + (n - 1))
		counter(n - 1)
	}
}
//output: loop 3, loop 2, loop 1, loop 0

//logic after recursion
void counter(int n) {
	if (n != 0) {
		counter(n - 1)
		print("loop " + (n - 1))
	}
}
//output: loop 0, loop 1, loop 2, loop 3

Iterative Pros

• memory usage is controlled explicitly by the programmer, so a ‘stack overflow’ is less likely

• can execute more quickly, as there is no overhead from stack frame creation/destruction

Iterative Con

naturally recursive functions can be harder to understand in an iterative form

Recursive Pros

• naturally recursive functions are much more concise when expressed this way

• languages which support tail recursion can eliminate some of the extra cost to performance, and stack overflows

Are Singly or Multiply Recursive Problems Easier to write Iteratively?

singly