Fun with Recursion

Pirates, coins and recursive logic.

500 pirates stumble across a booty of 100 gold coins.

The pirates have a very hierarchical power system, and they are numbered from 1 through 500 with #1 being the pirate king.

The pirate king proposes a way of distributing the gold coins (eg 500 to him 0 to everyone else) and all pirates vote. If at least 50% of votes approve of the distribution, then it is carried out. If not, then the pirate king is killed and #2 takes his place. And so on.

Assuming all pirates are rational and are perfect logicians, motivated by (in strictly descending order of priority): -Survival, Getting as much gold as possible, Murder is better than peaceful agreement.

What is the end outcome?

Though I didn’t know it at the time, a number of years ago (shortly before leaving school) I encountered a problem (included above) during one of my university interviews, which required me to utilise recursive logic as part of its solution. Have a go and see if you can solve it! (Hint: the number of coins may be less than you thought!)

Essentially, this technique is effective when a problem can best be solved by breaking it down into simpler cases. This often leads to a rather elegant solution to your problem.

More recently, having devoted my time to learning to code I encountered recursion again In a different context (detecting palindromes using Ruby code). In one early session at Flatiron school, whilst preparing for an upcoming coding test, my cohort was exposed to the following solution to a problem:

def palindrome?(string)
  if string.length == 1 || string.length == 0
    true
  else 
    if string[0] == string[-1]
      palindrome?(string[1..-2])
    else
      false
    end
  end
end

The above code was somewhat more impressive than my initial idea of passing the words in a string into an array before trying to manipulate the array. I was struck by the technique and started trying to find ways to use it in my own code. Later that same week- I had my chance, Whilst creating a small command line app mimicking the features of instagram (creatively titled CLInstagram), I recursion to direct users back to the main menu after performing a set of actions (such as following another user). The code is rather messy (and difficult to read, as far as code goes) but I’ve tried to highlight where I used recursion in bold:

def main_menu(x)
  exit_app = falsewhile(!exit_app) do
  puts “What do you want to do #{x.username}? “
  puts “1. View a profile”
  puts “2. View own profile”
  puts “3. Follow a user”
  puts “4. see the followers you have”
  puts “5. Log Out
  response=gets.chomp
 
  case response.to_i
    when 1
      desired= gets.chomp
      x.show_user_feed(desired.username)
    when 2
      x.show_user_feed(x.username)
    when 3
      desired= gets.chomp
      x.follow_user_via_username(desired)
      main_menu(x)
    when 4
      x.get_followers.each { |fol| puts fol.username}
      main_menu(x)
    when 5
      exit_app = true
      puts “See you next time!”
end

I was promptly urged by my project partner and switch to an interactive method, as (he informed me) that recursion has some drawbacks which make it less than ideal for most applications. However, I was impressed by the fact that (while seeming reasonably arcane,) this technique was useable in my third week of writing code.

At the end of this post, I will include a brief discussion of some of the pros and cons of recursive methods, but first I wanted to share some of the slick methods I’ve come across while playing and experimenting with this technique, for your enjoyment.

Example 1- Finding the nth term of a Fibonacci sequence

def fibonacci(n)
  if n <= 1
    return n
  else
    fibonacci( n — 1 ) + fibonacci( n — 2 )
end

The above function (which I understand is something of a classic in programming pedagogy) will return the nth term of the fibonacci sequence. Give it a go on Repl.it and be amazed.

Example 2- putting out all the numbers from n down to zero

def countdown(n)
  if n>=0
    # Base Case: Are we at zero yet?
    return if n.zero?
    puts n
    # Reduction Case: Shrink n to get closer to zero.
    countdown(n-1)
  else
    put "under zero"
end

Vaguely amusing: this function simply puts out every number from n until zero, like a small child asking “are we there yet”.

Example 3- Factorials

def factorial(n)
  if n == 0 
    1
  else
    n * factorial(n-1)
  end
end

Possibly my favourite, as (finding this) the previous method I had constructed (in my first week) looked like a monster in comparison. It’s plain from these methods alone that recursion can lead to some pretty nice logic and clear code… so what’s the problem?

What are some reasons to avoid using recursion

So, I’ve shown you some slick methods that use recursion (and perhaps I will again, when I’ve played with it some more). So what are the downsides- why isn’t it used all the time?

• It is usually slower to run than an iteration.
• It usually uses more memory.

What are some benefits to using recursion, and why might I use it at some point?

• Recursion adds clarity and (sometimes) reduces the time needed to write and debug code (but doesn’t necessarily reduce space requirements or speed of execution).
• Performs better in solving problems based on tree structures.

That’s all for now. Thanks for reading.