What's the best way to learn about recursive functions and tracing?

Question

For my class we are to learn about recursive functions in java. What is the best way to go about learning about recursion? How would you recommend tracing it? Thanks!

Answer 1

Well, recursion can simply be used anywhere where iteration can. Often iteration based algorithms are replaced witch recursive once at the stage of development, just because recursion is really simple and intuitive.

Abstract

Imagine a child told to collect bricks to the box. The child will most likely simply "pick one brick form the floor and put it in to the box" and "repeat this as long there are no more bricks on the floor". Every step child is asking itself, "Are there some more bricks I need to collect?", "Oh! Here is one, so I put it in to the box" or "No more bricks! I'm done". So such behavior, when mechanism is calling itself, is recursion. There are two things characterizing such algorithm:

• end of algorithm is clearly stated,
• "big", complex problem has been decomposed to elementary problems, and to problems on a lower level of complexity then the one we had at the beginning.

Example

Consider this recursive search function:

void search(int arr[], int left, int right, int x) {
  if (left > right)
    cout << "Element " << x << " been not found!\n";
  else
    if (tab[left] == x)
      cout << "Element " << x << " been found at position " << left << "\n";
    else
      search(tab, left + 1, right, x); // call search() witch updated properties
}

Our brains are doing math all the time, often much more complex then recursion.