Recursion

Definition:

  • Recursion is the name given to a programming technique in which repetition is achieved by having a function call itself. Non-recursive repetition is called iteration (looping).

Advantages:

  • It can provide very elegant solutions to tasks that are difficult to achieve iteratively, like deleting nodes in a binary tree.
  • In some languages, especially functional languages, recursion is the only way to achieve iteration. (Advanced: Because it does not use variables, recursion can be used to implement repetition without changing the program state. It is therefore safer in a distributed computing context because there are no side effects.)

Disadvantages:

  • You can run out of memory easily if the base case is not applied correctly.
  • Recursion can be quite confusing.

Tasks:

Create a page for recursion on your sites.

Add the definition, along with advantages and disadvantages. Make sure you understand them. What do I mean by the base case not being applied properly?

Write the following functions in Java both iteratively and recursively:

  • A factorial function
  • A function that takes an integer array and returns the sum of its contents.

Then we will start thinking about how to code a recursive solution to the Towers of Hanoi.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s