Topic 5 – 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.

Video – Recursion

Link – https://www.youtube.com/watch?v=m5McK2pMedw

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.

Video – Recursion

Link – https://www.youtube.com/watch?v=m5McK2pMedw