3-2-2 Recursion

Recursion describes the ability of a routine to call itself. This means a recursive routine is defined in terms of itself.

General case: the solution in terms of itself for a value of n.
Base case: a value that has a solution which does not involve any reference to the general case solution.

An example of a recursive routine would be n factorial.

function factorial is: input: integer n such that n >= 0 output: [n × (n-1) × (n-2) × … × 1] 1. if n is 0, return 1 2. otherwise, return [ n × factorial(n-1) ] end factorial The general case is n! = n * (n-1)! The base case is 1! = 1

Recursion works only if the routine is called with the current value or values passed as parameters. It would not work with global variables.

Each time a routine is called, a special area of main memory, called the stack, is used. There the return address is stored as well as the contents of registers. Any local variables and the routine's parameters are also known as a stack frame. When a routine ends, control normally passes to the stored return address and its stack frame is removed from the stack.

Stack Frame: the locations in the stack area used to store the values referring to one invocation of a routine.

Towers of Hanoi: Example