Recursion

Recursion means writing procedures and functions which call themselves.

Recursion involves:

• solving large problems
• by breaking them into smaller problems
• of identical forms

Eventually a "trivial" problem is reached that can be solved immediately.

Initially it may seem that the solution is incomplete.

General algorithm:

	if stopping condition then
		solve simple problem
	else
		use recursion to solve smaller problem(s)
		combine solutions from smaller problem(s)

Iterative vs Recursive

Recursion is a way of implementing a loop.

Iteration and recursion can always be interchanged.

iteration

• cognitively simple

recursion

• is not as intuitive
• demanding on machine time and memory
• sometimes simpler than iteration

Examples

The best way to understand recursion is to look at lots of examples:

• think of a number from 1 to N
• print a number
• evaluate a move in a game
• multiply numbers from 1 to N
• dual procedure recursion
• print permutations of a string
• binary search
• merge sort
• "Towers of Hanoi"
• solve a maze