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?)
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.
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...
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. 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.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)
}
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)
}
new Function[Int, Int] {...}. Thank you!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...
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
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))
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)
f, which is not anonymous. The fact that it's defined inside of an anonymous function does not change that.
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