Anonymous recursive function in Scala

Question

Is there a way to write an anonymous function that is recursive in Scala? I'm thinking of something like this:

((t: Tree) => {
    print(t.value);
    for (c <- t.children)
        thisMethod(c)
})(root)

(Related question: Which languages support *recursive* function literals / anonymous functions?)

Answer 1

As described in the link you posted. You can use Y-combinator. Here is example:

scala> def fix[A,B](f: (A=>B)=>(A=>B)): A=>B = f(fix(f))(_)
fix: [A,B](f: ((A) => B) => (A) => B)(A) => B

scala> val fact = fix[Int,Int](f => a => if(a<=0) 1 else f(a-1) * a)
fact: (Int) => Int = <function1>

scala> fact(12)
res0: Int = 479001600

Note it doesn't work with big numbers. Be careful with tail call optimization.

Answer 2

If you don't want to hit the "Amazing mathematics" you could just revert to the object aspects of scala.

val fact = new Function1[Int,Int]{
    def apply(x:Int):Int = if(x==1) x else x * apply(x-1)
}

Answer 3

in order to make it look geekier you can also use this code style:

val fact = new ((Int) => Int){
  def apply(x:Int):Int = if(x==1) x else x * apply(x-1)
}

Answer 4

Adding to the many good responses here in this thread, the fact that Scala is not giving us tail call optimizable Fixed-point combinator has been bothering me so much so that I've decided to write a macro to translate Y-combinator-like call to an ordinary, idiomatic recursive call (with tail call optimization, of course). The idea is that a call like

fix[Int,Int]((next) => (y) => ...body...)

is readily translatable into

({(input) =>
  object next {
    def apply(y:Int):Int = ...body...
  }
  next(input)
})

I've put up macro implementation targeting Scala 2.11 (with minor tweak should also work with 2.10) into this gist.

With this macro, we can perform ordinary recursive tasks in anonymous manner without fearing stack overflow e.g.

import asia.blip.ymacro.YMacro._
(y[BigInt,BigInt]((xx) => (y) => if(y==1) 1 else y * xx(y-1)))(2000)

gives

res0: BigInt = 33162750924506332411753933805763240382811...

Answer 5

Recursive calls on Scala. Let me take sum of N numbers example for recursion

var sumIt:(Int => Int) = (x: Int) => {if(x<=1) 1 else sumIt(x-1)+x}


 scala> sumIt(10) 
val res141: Int = 55

You can see the sumIt has its type with Int, Int as Input and the return value. The sumIt lambda function takes as argument which is an Integer and it does recursive call on sumIt.

I just this example for easy understanding the recursion call. You can direct formula for this logic like...

sumValue = (N*(N+1)) /2

Answer 6

To add onto @in-ho-yi 's answer. For simplicity you can directly define a local function inside of an anonymous function and use it for recursion. Also using @tailrec before the local function you can make sure it will apply tail recursion which you can't do with the Y-combinator.

This is a better approach than Y-combinator because it only adds 2 frames to the stack and 1 per call of the function (if it's not tail recursive, if it is it will only add 1 in total so 3 frames max will be used) instead of 6 per call that Y-combinator uses

import scala.annotation.tailrec

val fact = {(input: BigInt)=>
  @tailrec
  def f(x:BigInt, acc: BigInt = 1):BigInt = {
    if(x<=1) acc
    else f(x-1, x*acc)
  }
  f(input)
}

print(fact(1024))

Answer 7

A very simple approach:

val fact = { (x: Int) =>
  def f(x: Int): Int = if (x == 0) 1 else x * f(x-1)
  f(x)
}

// Use as anonymous function below
(1 to 5).map { (x: Int) =>
  def f(x: Int): Int = if (x == 0) 1 else x * f(x-1)
  f(x)
}

// res0: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 6, 24, 120)