Turning a while loop into a recursive function

March 27, 2008 at 9:21 pm Leave a comment

A Decorative PictureThis is terribly simple, but it would appear I didn’t really know it for at least 20 years of my life, so it’s perhaps worth writing it down. (I suspect this is a consequence of working in languages which didn’t have tuple types):

Any while loop can be turned into a recursive function by doing little more than moving text around.

We can think of all while loops as doing the following:

state = init_state
constants = init_consts
while condition(state):
    state = f(state, constants)

Here state is shorthand for “everything that the while loop changes” whilst it is running, and f is shorthand for “the changes that the loop code makes”.

Given this generalized while loop we can rewrite this as:

def loop_func(state, constants):
    if condition(state):
         return loop_func(f(state, constants), constants)
        return state

state = loop_func(init_state, init_constants)

and life is once again incredibly dull.

Going the other way, if you have a recursive function (not mutually recursive) like so

def f(state):
   if end_state(state):
       return f_known(state)
   new_state = change_state(state)
   return f(new_state)

then you can turn it into a while loop like this:

while not end_state(state):
      state = change_state(state)
return f_known(state)

Again, this is terribly simple once you start writing it down for yourself (though perhaps not if you are reading someone else write it)

Post script
This also happens to let you write a “while function” which is analogous to the reduce function, though this seems to be noticeably lacking from haskell (I might just be mistaken about this). Perhaps, it is considered to produce code that is hard to read. This would look something like:

def while_reduce(condition, state_change, init_state):
         if condition(init_state):
                 return while_condition(condition, state_change, state_change(init_state)
                return init_state

Entry filed under: Uncategorized. Tags: .

Ant troubleshooting A local firewall for ubuntu

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed

March 2008
« Feb   Apr »

%d bloggers like this: