Topic - Recursive Problems and Recursion

Concept of Recursion

To understand how recursion works - you must first understand the concept of a stack ( Topic - Stacks and Queues ). Because calls to computer functions are held on a stack, recursion follows the pattern of a stack. The classic example of recursion is the calculation of the Factorial of a number. As an example 4! (read 4 Factorial) is the product of 4 * 3 * 2 * 1. The is is easily calculated with recursion - with a simple function

function Factorial(x) {

       if (x != 0) return x * Factorial(x-1);

       return 1;

}

When called with 4 as the argument - the return is 4*Factorial(3) - with a little work it is easy to see how you can get the answer.

Linked Lists and Recursion

You have been using recursion in the implementation of a linked list. The concept is pretty simple, since each list element has a value and a link to the next element

Element X(i) { value, Pointer to next element }

To print all the elements of X, you simply print the value of X(i) and then pass the pointer to the function to do the next element. Remember - you will need a terminating element. You will see in upcoming topics how recursion allows us to set up much more complex structures, such as trees - which add all sorts of capabilities.

Recursion Lectures

Recursion is covered in Lecture 3.2 in All Course Lectures

Articles on Recursion

Wikipedia has a fantastic article on recursion (thank all the folks who contributed) with all the class examples. You should read the entire article at http://en.wikipedia.org/wiki/Recursion_%28computer_science%29 and be sure to go through each of the recursion examples. 

I also recommend the Khan academy video series on recursion - they will come in quite handy for some of the assignments. https://www.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/recursion Though recursion is not conceptually challenging - the capabilities that become available with recursion can be quite complex - and we will be getting into those soon.