What is recursion?

• A recursive function is fuction that calls itself.

Structure of recursion

• Recursive functions contain at least one base case, which halts the recursion, and at least one recursive call.
• Each recursive call has its own set of local variables, including its parameters.
• Parameter values capture the progress of a recursive process, much like loop control variable values capture the progress of a loop.

Uses of recursion

• Recursion can be used to traverse linear structures like string and arrays but it is most useful for traversing tree structures which are difficult to traverse with simple loops.
• Any recursive solution can be replicated through the use of an iterative approach. However some recursions, such as tree recursions, will require maintaining extra data structures to keep track of the information that would otherwise be managed by the process of recursion.