I recently had a phone interview for a position as a software engineer and one of the questions I was asked was to define iteration and recursion and explain the differences between the two. I knew what iteration was, but drew a complete blank when it came to recursion. I've to decided to take this opportunity to write about it and try to explain the differences between the two.

Definitions from good old Wikipedia

Iteration - The act of repeating a process with the aim of approaching a desired goal, target or result.

Recursion - The process of repeating items in a self-similar way.

Digging deeper

Iteration

In my own words as related to computer science I would define iteration as a way of repeating an operation a certain number of times or until a certain condition is met. The most common occurrence of iteration that I come across is the act of looping through an array of values. Here's a few examples of iteration written in Ruby that will produce the same result of printing out the numbers 1 through 10.

# times method
10.times do |i|
  puts i + 1
end

# each method on a range
(1..10).each do |val|
  puts val
end

# while loop
i = 1
while i <= 10
  puts i
  i += 1
end

# for loop
for i in 1..10
  puts i
end

Recursion

I would describe recursion as calling a method or function from within itself. At first it sounded like this could cause an infinite loop, but if you set a conditional then the function will perform until a conditional is met. Here's the 1 to 10 example using recursion.

def plus_one(i)
  puts i
  plus_one(i+1) if i < 10
end

# call the method
plus_one(1)

I hadn't put much thought into it before, but I realize that I have been using recursion on almost a daily basis. I've noticed that I have to attach the -r flag to the bash command cp when I want to copy over the entire contents of the folder and all of its subdirectories. I don't know all the details, but the recursive flag basically calls the cp command again in each subdirectory and so own.

There appear to be limits on recursion in the Ruby programming language, because if I try the recursion example and change it to print from 1 to 10,000, then I get the following error after the 9,340 time:

SystemStackError: stack level too deep

I would appreciate any comments or thoughts as to why this occurs.

Thoughts on Iteration and Recursion

As seen above you could produce a similar result whether or not you use iteration or recursion. For the 1 to 10 example it makes more sense to use iteration for simplicity sake. I imagine that recursion could come in handy for a more complicated task.