Recursion wins!

I recently read the little schemer and that got me thinking about recursion and loops.

After starting my programming life with Python, I normally use for-loops to solve problems. But actually they are an inferior mechanism when compared to recursion, if (and only if) the language provides proper syntactic support for that. Since that claim pretty much damns Python on a theoretical level (even though it is still a very good tool in practice and I still love it!), I want to share a simplified version of the code which made me realize this.

Let’s begin with how I would write that code in Python.

res = ""
instring = False
for letter in text:
    if letter = "\"":
        # special conditions for string handling go here
        # lots of special conditions
        # and more special conditions
        # which cannot easily be moved out, 
        # because we cannot skip multiple letters
        # in one step
        instring = not instring
    if instring:
        res += letter
        continue
    # other cases

Did you spot the comment “special conditions go here”? That’s the point which damns for-loops: You cannot easily factor out these special conditions.1 In this example all the complexity is in the variable instring. But depending on the usecase, this could require lots of different states being tracked within the loop and cluttering up the namespace as well as entangling complexity from different parts of the loop.

This is how the same could be done with proper let-recursion:

; first get SRFI-71: multi-value let for syntactic support for what I
; want to do
use-modules : srfi srfi-71

let process-text
    : res ""
      letter : string-take text 1
      unprocessed : string-drop text 1
    when : equal? letter "\""
           let-values 
               ; all the complexity of string-handling is neatly
               ; confined in the helper-function consume-string
               : (to-res next-letter still-unprocessed) : consume-string unprocessed
               process-text
                   string-append res to-res
                   . next-letter
                   . still-unprocessed
    ; other cases

The basic code for recursion is a bit longer, because the new values in the next step of the processing are given explicitly. But it is almost trivial to shell out parts of the loop to another function. It just needs to return the next state of the recursion.

And that’s what consume-string does:

define : consume-string text
    let
        : res ""
          next-letter : string-take text 1
          unprocessed : string-drop text 1
        ; lots of special handling here
        values res next-letter unprocessed

To recite from the Zen of Python:

Explicit is better than implicit.

It’s funny to see how Guile Scheme allows me to follow that principle more thoroughly than Python.

(I love Python, but this is a case where Scheme simply wins - and I’m not afraid to admit that)

PS: Actually I found this technique when thinking about use-cases for multiple return-values of functions.

PPS: This example uses wisp-syntax for the scheme-examples to avoid killing Pythonistas with parens.


  1. While you cannot factor out parts of for loops easily, functions which pass around iterators get pretty close to the expressivity of tail recursion. They might even go a bit further and I already missed them for some scheme code where I needed to generate expressions step by step from a function which always returned an unspecified number of expressions per call. If Python continues to make it easier to use iterators, they could reduce the impact of the points I make in this article. 

AnhangGröße
2014-03-05-Mi-recursion-wins.org3.36 KB

Use Node:

⚙ Babcom is trying to load the comments ⚙

This textbox will disappear when the comments have been loaded.

If the box below shows an error-page, you need to install Freenet with the Sone-Plugin or set the node-path to your freenet node and click the Reload Comments button (or return).

If you see something like Invalid key: java.net.MalformedURLException: There is no @ in that URI! (Sone/search.html), you need to setup Sone and the Web of Trust

If you had Javascript enabled, you would see comments for this page instead of the Sone page of the sites author.

Note: To make a comment which isn’t a reply visible to others here, include a link to this site somewhere in the text of your comment. It will then show up here. To ensure that I get notified of your comment, also include my Sone-ID.

Link to this site and my Sone ID: sone://6~ZDYdvAgMoUfG6M5Kwi7SQqyS-gTcyFeaNN1Pf3FvY

This spam-resistant comment-field is made with babcom.

Inhalt abgleichen
Willkommen im Weltenwald!
((λ()'Dr.ArneBab))



Beliebte Inhalte

Draketo neu: Beiträge

Ein Würfel System

sn.1w6.org news