How to write recursive anonymous functions?

Question

In my ongoing effort to learn about scala, I am working on Odersky's “Example Scala” and in the chapter on first-class functions, the section on anonymous functions avoids the situation of a recursive anonymous function. I have a solution that seems to work. I am curious if there is a better answer.

From pdf: Code for displaying higher-order functions

def sum(f: Int => Int, a: Int, b: Int): Int = if (a > b) 0 else f(a) + sum(f, a + 1, b) def id(x: Int): Int = x def square(x: Int): Int = x * x def powerOfTwo(x: Int): Int = if (x == 0) 1 else 2 * powerOfTwo(x-1) def sumInts(a: Int, b: Int): Int = sum(id, a, b) def sumSquares(a: Int, b: Int): Int = sum(square, a, b) def sumPowersOfTwo(a: Int, b: Int): Int = sum(powerOfTwo, a, b) scala> sumPowersOfTwo(2,3) res0: Int = 12 

from pdf: Code for anonymous functions

 def sum(f: Int => Int, a: Int, b: Int): Int = if (a > b) 0 else f(a) + sum(f, a + 1, b) def sumInts(a: Int, b: Int): Int = sum((x: Int) => x, a, b) def sumSquares(a: Int, b: Int): Int = sum((x: Int) => x * x, a, b) // no sumPowersOfTwo 

My code is:

 def sumPowersOfTwo(a: Int, b: Int): Int = sum((x: Int) => { def f(y:Int):Int = if (y==0) 1 else 2 * f(y-1); f(x) }, a, b) scala> sumPowersOfTwo(2,3) res0: Int = 12 

Answer 1

What is it worth ... (the name and the "real question" do not quite agree)

Recursive anonymous function objects can be created using the FunctionN long-hand , and then using this(...) inside apply .

 (new Function1[Int,Unit] { def apply(x: Int) { println("" + x) if (x > 1) this(x - 1) } })(10) 

However, the amount of negligence that usually introduces makes the approach generally less ideal. It is best to use a "name" and have a more descriptive, modular code - not that there is a very good argument for this :-)

 val printingCounter: (Int) => Unit = (x: Int) => { println("" + x) if (x > 1) printingCounter(x - 1) } printingCounter(10) 

Happy coding.

Answer 2

You can generalize this indirect recursion to:

 case class Rec[I, O](fn : (I => O, I) => O) extends (I => O) { def apply(v : I) = fn(this, v) } 

Now the amount can be written using indirect recursion as:

 val sum = Rec[Int, Int]((f, v) => if (v == 0) 0 else v + f(v - 1)) 

The same solution can be used to implement memoization, for example.