A very simple recursive function

This is for Louis Sterrett. It seems to me that, when explaining recursion in programming, it’s easier for many people to start with imperative, rather than functional, examples. The simplest sort is an endless loop; next simplest would be a loop that constantly executes an action; and next simplest after that would be a loop that (say) uses recursion to perform an action 10 times, using a parameter to do the counting down. (Or possibly, it might be helpful to show how recursive definitions work – e.g. ancestor of X is their immediate parents, plus the recursive closure of the “is-parent-of” relation?) I should really write this up properly, but in the meantime, here’s the simple example I used to try and explain recursion in Python. It’s very lacking in detail. You probably had to be there to understand it. Don’t read it.

You’ve developed a robot, controlled by a Python program, which can screw in lightbulbs. It has an infinite store of lightbulbs, and you’ve developed a program so that, pointed at a row of empty light-sockets, it can screw lightbulbs into all of them.

Your program contains the following function:

def change_lightbulb_row():
have_empty_light_sockets = detect_empty_light_sockets()     # returns True or False
if have_empty_light_sockets:
go_to_rightmost_empty_light_socket()
screw_in_lightbulb()
change_lightbulb_row()

(The functions “detect_empty_light_sockets“, “go_to_rightmost_empty_light_socket” and “screw_in_lightbulb” turn out to be trivial to program, so are not included here.)

Notice that the function calls itself, in the last line: that’s recursion.

You could equally well have written this function with a while loop:

def change_lightbulb_row():
have_empty_light_sockets = detect_empty_light_sockets()     # returns True or False
while have_empty_light_sockets:
go_to_rightmost_empty_light_socket()
screw_in_lightbulb()
have_empty_light_sockets = detect_empty_light_sockets()

In fact, all recursive functions can be rewritten using loops, and vice versa.

For a slightly more complex example of recursion, check out Udacity.

Advertisements

7 thoughts on “A very simple recursive function

    1. gravbeast Post author

      Ah – if you follow it through carefully though, it only calls itself again if there’s more lightbulbs still to be changed.

      Consider what would happen if you pointed it at a row of lights which were all already screwed in.

      It’d execute “have_empty_light_sockets = detect_empty_light_sockets()“, and decide this equalled “False”.

      It’d get to "if have_empty_light_sockets:", and then, because the answer would be “False”, it just wouldn’t call itself any more – the function would return. Does that make sense?

      (Edited: oops, I had a “True” instead of “False” there for a second.)

    2. gravbeast Post author

      An infinite loop would look more like this:


      def change_lightbulb_row():
        go_to_rightmost_empty_light_socket()
        screw_in_lightbulb()
        change_lightbulb_row()

      There’s no “if” statement to test whether there’s more unfilled lightbulbs, so it just keeps calling itself ad infinitum.

  1. Louis Sterrett

    So this helps us by allowing us to not have to do an additional loop through the lightbulbs in which we’d use the function on each? Like so:

    def change_lightbulb(empty_socket):
      screw_in_lightbulb(empty_socket)

    For socket in list_of_empty_sockets:
      change_lightbulb(socket)

    1. gravbeast Post author

      I fixed the indenting for you.

      So: in my post, I’ve assumed we don’t have access to a “list of empty sockets”: our robot can detect whether there’s an empty light-socket in its field of vision, and can move rightwards ’til it gets to the right-most empty light-socket, but it doesn’t yet have a “list” of empty sockets; and our function “screw_in_lightbulb” just consists of the robot reaching directly out in front of itself, and screwing in a lightbulb to whatever is there. (Hopefully, an empty socket.)

      If our robot was smart enough to recognize multiple empty sockets, and put them in a list, then yes, we could use a “for” loop. I’d probably write it like this:

      def change_lightbulb_row():
        list_of_empty_sockets = identify_list_of_empty_sockets() # returns a list of sockets
        for socket in list_of_empty_sockets:
          go_to_socket(socket)
          screw_in_lightbulb()

      I’ve assumed that we now have a function “go_to_socket()“, so we can make use of the list.

      If it doesn’t make much sense yet, I wouldn’t really worry, since like I said, anything you can do with recursion, you can do with loops instead. So get loops under control, and you can always come back to it later.

      Some problems naturally lend themselves to being expressed in a recursive way, and for those problems, recursion provides a way of writing an elegant solution – but a solution with loops will also work, it may just be a bit harder for someone to read.

      As an example, many mathematical concepts are defined recursively, and the Udacity page gives some examples.

      For instance, factorial(n): if n is 0, then factorial(n) is defined as 1. If n is greater than 0, then factorial(n) is defined as “n * factorial(n-1)”.

      So factorial(3) is equal to 3 * factorial(2);
      which is equal to 3 * 2 * factorial(1);
      which is equal to 3 * 2 * 1 * factorial(0);
      which is equal to 3 * 2 * 1 * 1.

      So the final result for factorial(3) is 3 * 2 * 1 * 1, or 6.

      I might re-write the post in a little while to try and make it clearer.

Comments are closed.