Anonymous recursive function in Scala

scala recursion anonymous-function
aioobe picture aioobe · Mar 17, 2011 · Viewed 7.2k times · Source

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

Rustem Suniev picture Rustem Suniev · Mar 17, 2011

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.

Related questions

How to call a method n times in Scala?

I have a case where I want to call a method n times, where n is an Int. Is there a good way to do this in a "functional" way in Scala? case class Event(name: String, quantity: Int, value: …

Read More
Scala - convert List of Lists into a single List: List[List[A]] to List[A]

What's the best way to convert a List of Lists in scala (2.9)? I have a list: List[List[A]] which I want to convert into List[A] How can that be achieved recursively? Or is there any other better way?

Read More
Reverse list Scala

Given the following code: import scala.util.Random object Reverser { // Fails for big list def reverseList[A](list : List[A]) : List[A] = { list match { case Nil => list case (x :: xs) => reverseList(xs) ::: List(x) } } // Works def reverseList2[A](…

Read More