| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Finally, you can manage your Google Docs, uploads, and email attachments (plus Dropbox and Slack files) in one convenient place. Claim a free account, and in less than 2 minutes, Dokkio (from the makers of PBworks) can automatically organize your content for you.

View
 

Topic - Recursive problems

Page history last edited by Dr. Ron Eaglin 4 years, 7 months ago

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.

 

Comments (0)

You don't have permission to comment on this page.