CODEWITHSUNDEEP
recursionf#functional-programming
Avrohom Yisroel
Avrohom Yisroel

Reputation: 9460

Why use a recursive function rather than `while true do` in F#?

Whilst watching a Pluralsight course by Tomas Petricek (who I assume knows what he is talking about), I saw code like the following...

let echo =
  MailboxProcessor<string>.Start(fun inbox ->
    async {
      while do true
        let! msg = inbox.Receive()
    printfn "Hello %s" msg
    })

Ignore the fact that this was to demo agents, I'm interested in the inner function, which uses while do true to keep it running indefinitely.

Whilst looking around for other example of agents, I saw that many other people use code like this...

let counter =
  MailboxProcessor.Start(fun inbox ->
    let rec loop n =
      async { do printfn "n = %d, waiting..." n
        let! msg = inbox.Receive()
        return! loop(n+msg) }
    loop 0)

Code copied from Wikibooks.

The inner function here is recursive, and is started off by calling it with a base value before the main function declaration ends.

Now I realise that in the second case recursion is a handy way of passing a private value to the inner function without having to use a mutable local value, but is there any other reason to use recursion here rather than while do true? Would there be any benefit in writing the first code snippet using recursion?

I find the non-recursive version much easier to read (subjective opinion of course), which seems like a good reason to use that whenever possible.

Upvotes: 4

Views: 1088

Answers (3)

Just another metaprogrammer
Just another metaprogrammer

Reputation: 11577

In F# for and while loop expressions lacks capabilities common in other languages:

  1. continue - Skip the rest of the loop and restart from the top of loop expression.
  2. break - Stop the loop prematurely.

If you want continue and break don't do what I did in the beginning a write a very complex test expression for while loops. Instead tail recursion is the best answer in F#:

let vs : int [] = ...
let rec findPositiveNumberIndex i =
  if i < vs.Length then
    if vs.[i] > 0 then 
      Some i
    else 
      findPositiveNumberIndex (i + 1)
  else
    None
match findPositiveNumberIndex 0 with
| Some i -> printfn "First positive number index: %d" i
| None   -> printfn "No positive numbers found"

In code like this F# applies something call tail-call optimization (TCO) which transforms the code above into a while loop with break. This means that we won't run out of stack space and the loop is efficient. TCO is a feature that C# lacks so we don't want to write code like above in C#.

Like others are saying with tail recursion you can sometimes avoid mutable state but that's not all.

With tail recursion your loop expressions can return a result which is nice.

In addition, if you like to iterate fast in F# over types like int64 or with increment other than 1 and -1 you have to rely on tail recursion. The reason is that F# only does efficient for expressions for ints and increments of 1 and -1.

for i in 0..100 do
  printfn "This is a fast loop"

for i in 0..2..100 do
  printfn "This is a slow loop"  

for i in 0L..100L do
  printfn "This is a slow loop"

Sometimes when you are hunting for performance a trick is to loop towards 0 (saves a CPU register). Unfortunately the way the F# generates for loop code this doesn't perform as well one would hope:

for i = 100 downto 0 do
  printfn "Unfortunately this is not as efficient as it can be"

Tail recursion towards 0 saves the CPU register.

(Unfortunately the F# compiler don't merge the test and the loop instruction for tail-recursion so it's not so good as it could be)

Upvotes: 2

Tomas Petricek
Tomas Petricek

Reputation: 243061

Talking about MailboxProcessor specifically, I think the choice depends on what exactly you are doing. In general, you can always use while loop or recursion.

Recursion makes it easier to use immutable state and I find while loop nicer if you have no state or if you use mutable state. Using mutable state is often quite useful, because MailboxProcessor protects you from concurrent accesses and you can keep the state local, so things like Dictionary (efficient hash table) are often useful.

In general:

  • If you don't need any state, I would prefer while
  • If you have mutable state (like Dictionary or ResizeArray), I'd go for while
  • If you have some immutable state (like functional list or an integer), then recursion is nicer
  • If your logic switches between multiple modes of operation then you can write it as two mutually recursive functions, which is not doable nicely with loops.

Upvotes: 15

dinnbot
dinnbot

Reputation: 64

In many cases it depends on how you like to code. Like in your example. Everything you can write recursiv you can also write with a loop, but sometime like with recursive data structures it is easier to write the in a recursive style. At university I learned that with recursive programming you only have to look at your next step which is pretty handy!

You might be interested in this question as it explains my answer a bit further: recursion versus iteration

Upvotes: 3

Related Questions