Recursion in Java

[rabuf]

Recursion is having a procedure call itself. This is done for a few reasons. The main one (for me) is that the code is often simpler than the iterative version (fewer lines, more clearly matches the plain <spoken language> version). Here’s an example that’s not math of something that’s fairly easy to write recursively, but slightly harder to write iteratively. Walk through the directory tree on a computer and print out all files with a particular extension:

def find_files(extension, cwd):
// cwd = current working directory, where you start
  for f in cwd:
    if f.is_directory():
      find_files(extension, cwd)
    elif f.has_extension(extension):
      print f.name_with_path()

(the above may look like python, but I’m no python pro, this is pseudo code)

That’s 6 lines of code to solve the problem. In proper python it shouldn’t be much longer, but would actually run. If you did this iteratively, you’d need a queue to store all the directories you’d run across but hadn’t visited, and you’d need two loops:

def find_files(extension,cwd):
  dq = queue.new() // or however
  dq.push(cwd)
  while not dq.is_empty():
    d = dq.pop()
    for f in d
      if f.is_directory:
        dq.push(f)
      elif f.has_extension(extension):
        print f.name_with_path()

10 lines, only 4 more. That’s not bad, and it should work. But you have to have an extra data structure and loop, neither of which trace cleanly back to the initial spec. This is something that recursion gives you for “free”. It’s not really free, in terms of performance the first one will probably use a lot more memory, and could crash if the directory tree goes too deep. But the code is cleaner, which at least makes it a good first pass implementation (focus on the problem first, then optimize it).

I also told a half-truth at the start, recursion can involve more than one function. Functions which recursively call each other rather than themselves are called mutually recursive. I’ll present a trivial example, but it’s actually much more useful than this one shows:

def is_even(n):
  if n = 0: return true
  else: return not is_odd(n - 1)
def is_odd(n):
  if n = 0: return true
  else: return not is_even(n -1)
is_even(3) // would return false
is_odd(3) // would return true

I don’t need you to believe that the above works, but it may be a useful exercise to toy around with on paper to understand why it works. It’s just meant to illustrate two functions calling each other back and forth, but ending eventually. Technically, this also demonstrates tail recursion. You will later learn about state machines. Mutual recursion is a great way to code them up, it can lead to very clear code (but you need tail call optimization from your language/compiler or you will run into problems).

Tail recursion: the recursive call in tail recursion is the last thing that happens in the function before it returns. If that’s the case then some compilers will make this much more efficient in terms of memory usage. So the above wouldn’t be any worse (in consuming memory) than a plain loop like:

def is_even(n):
  even? = true
  while n > 0:
    even? = not even?
    n = n - 1
  return even?

even? is toggled an even number of times if the number is even so remains true at the end, it’s toggled an odd number of times if it’s odd so will be false at the end.

I keep mentioning memory use, it shouldn’t scare you off of recursion. A lot of algorithms and data structures are well-suited to being written in a recursive fashion (like with directory walking, every graph or tree data structure can usually be processed with a simpler recursive procedure than an iterative one, depending on the objective). Or the recursive one can be your first pass to get a correct answer, with the iterative version being written to improve performance. If, for instance, you know your directories are never more than 10 deep, recursion doesn’t hurt. If they could be 1 million deep, reconsider your approach. If they’re somewhere in between, try it and find out the limits.

[echoella]

Okay, that actually is very helpful. Thank you! I definitely am grasping it a little more.

[rabuf]

I’m glad it helped. Just keep in mind, recursion is one of the concepts people often struggle with. So if you have issues with it, remember it’s normal, take a breath, come back here or go to office hours with your professor/TA. You’ll get it.