# 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:

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

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