CODEWITHSUNDEEP
scalarecursion
Andrey
Andrey

Reputation: 800

Use a recursive call in List.map

I have a problem with list operations in Scala. I'm trying to implement the same logic, that I've implemented sequentially in Java (and it worked) but it returns 0 which I not expected. I've debugged the list operations as I could (replaced provided map call to sequence of lists, which behaves as intended), but I can't trace the last step (map list members to the recursive call of this function). Can you provide some thoughts about my approach?

@tailrec
def a(b: Int, cList: List[Int]): Int = {
    if (b == 0) 1
    else if (cList.isEmpty) 0
    else
      List.range(0, b / cList.head).
        map(n => a(b - n * cList.head, cList.tail)). 
        foldLeft(0)((b, a) => b + a)
  }

I suppose, that before foldLeft the list must contain a result of the recursive call for all elements. Does such a call work? For clarity I enclose my Java program, that behaves as supposed:

private static int a(int b, int[] cList) {
        if (b == 0) {
            return 1;
        } else {
            if (cList.length == 0)
                return 0;

            int head = cList[0];
            int[] tail = Arrays.copyOfRange(cList, 1, cList.length);
            int x = b / head;
            int sum = 0;
            for (int i = 0; i <= x; i++) {
                sum += a(b - (i * head), tail);
            }
            return sum;
        }
    }

Upvotes: 1

Views: 829

Answers (1)

Sergey Passichenko
Sergey Passichenko

Reputation: 6930

Check documentation for List.range:

a $coll with values start, start + 1, ..., end - 1

Additional notes:

  • In your case tail call optimization isn't available.
  • .foldLeft(0)((b, a) => b + a) equals to .sum
  • You mix imperative loop solution with recursion, try to use only recursive list processing

Upvotes: 2

Related Questions