46

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?)

Community
  • 1
  • 1
aioobe
  • 399,198
  • 105
  • 792
  • 807

6 Answers6

54

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.

FMM
  • 4,219
  • 1
  • 24
  • 44
Rustem Suniev
  • 1,149
  • 9
  • 8
  • 11
    "Amazing" in the original sense of making me feel like I'm lost in a maze. `fix` is a function takes as input a function that itself takes a single argument and returns another function that takes a single argument, and then it ... OK, I'm going to need a better explanation from *somebody*... – Michael Lorton Mar 17 '11 at 22:59
  • But this does not allow tail call optimization, am I correct? – fresskoma Jun 02 '11 at 21:36
  • 8
    @Malvolio: `fix` is a function which takes another function `f` as its argument and returns a _fixed point_ for that function, i.e. a value `x` for which `f(x) == x`. Functions which compute fixed points for other functions are called [fixed point combinators](http://en.wikipedia.org/wiki/Fixed_point_combinator). The Y-combinator is just one example of a fixed point combinator. Fixed point combinators offer a way to describe recursion in languages such as the lambda calculus which don't allow self-referential definitions. – Tom Crockett Jun 25 '11 at 01:14
26

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)
}
The Archetypal Paul
  • 40,359
  • 19
  • 100
  • 131
Spangaer
  • 381
  • 3
  • 3
14

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)
}
Peter Ertl
  • 199
  • 1
  • 4
6

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...
In-Ho Yi
  • 968
  • 1
  • 8
  • 12
  • I guess I'm still wondering whether you can add the tailrec annotation so it can have the tail call optimization. – Josh Cason Mar 15 '16 at 19:54
  • @JoshCason think Scala is smart enough to infer tailrec in the example that I gave. I'm not too sure about more involved use cases to be honest. – In-Ho Yi Oct 19 '16 at 23:44
1

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
Nithishkumar K R
  • 121
  • 1
  • 6
-1

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)
pvillela
  • 521
  • 1
  • 6
  • 8
  • The recursive function is `f`, which is not anonymous. The fact that it's defined inside of an anonymous function does not change that. – nafg Oct 21 '18 at 21:58
  • The downvote is unwarranted as the solution serves the purpose intended by the question. In addition, you singled-out this solution while there are two other solutions above very similar to this one that use def apply instead of def f. – pvillela Oct 23 '18 at 13:09
  • Is your solution more correct the way it is than if `def f` were moved up one line? Because if no that illustrates my point, and if yes explain why they aren't exactly the same except for f's scope – nafg Oct 24 '18 at 16:07