Credits for Lecturing and Authoring
What is Recursion?
Recursion
Example of Recursion
Trace of Multiply

Any function which calls itself, or indirectly calls itself is called a recursive function.

Generally, a recursive solution is less efficient than an iterative solution in terms of processing usage. This is due to the extra function calls which are not made with an iterative solution. The reason to study recursive functions at all is because they offer natural, simple solutions to otherwise very difficult problems.

Good recursive problems have the following characteristics:

simple cases have straightforward, nonrecursive solutions

other cases can be redefined in closer terms to those of the simple case

able to reapply the definition process every time the recursive function is called, reducing the function entirely to simple cases.

Recursion

Most recursive algorithms are of the following form:

if this is a simple case (or base case) solve it
else redefine the problem using recursion

Let's assume we have a problem of size n. Assume we are able to split this problem into two more problems, of sizes n-1 and 1. We recursively perform the same operation on the problem of size n-1 until we have n problems of size 1 (simplest cases), which are easily solved.

Example of Recursion

Problem:  Multiply 6 by 3.

Steps:  Split into two problems:

            1. Multiply 6 by 2.

            2. Add 6 to the result of problem 1.

        Again split problem 1 into two problems.

            1. Multiply 6 by 2.

               1.1 Multiply 6 by 1.

               1.2 Add 6 to the result.

            2. Add 6 to the result of problem 1.

Tracing the execution of a recursive program helps us understand how it really works. We will now trace the execution of the function call multiply(6,3) by drawing an activation frame corresponding to each call of the function. Activation frames summarize the execution of the call. Just follow the arrows.