# Fast Recursive Java Solution

• Base solution is here. We declare the recurrence:

``````Recurrence:
canCross(pos, speed) =
canCross(pos+speed, speed) ||
speed > 1 && canCross(pos+speed-1, speed-1) ||
canCross(pos+speed+1, speed+1)

Base case:
1. canCross(pos=stones[LastIndex], ?) = true
2. canCross(pos>stones[LastIndex], ?) = false
``````
``````public class Solution {
private boolean canCross(Set<Integer> s, int end, int curr, int speed) {
if(curr >= end) {
return curr == end;
}

return s.contains(curr+speed) && canCross(s, end, curr+speed, speed) ||
s.contains(curr+speed+1) && canCross(s, end, curr+speed+1, speed+1) ||
speed > 1 && s.contains(curr+speed-1) && canCross(s, end, curr+speed-1, speed-1);
}

public boolean canCross(int[] stones) {
Set<Integer> s = new HashSet<>();
for(int n : stones) {
}

if(s.contains(stones[0] + 1)) {
return canCross(s, stones[stones.length-1], stones[0] + 1, 1);
} else {
return false;
}
}
}
``````

If you submit the above code, you get TLE.
Now it is time to optimize your algorithm with cache.

Why we need a cache? Because the recursion will produce duplicate subproblem.

``````public class Solution {
private String ck(int a, int b) {
return String.valueOf(a) + "@" + String.valueOf(b);
}

private boolean canCross(Set<Integer> s, int end, int curr, int speed, Map<String, Boolean> cache) {
if(curr >= end) {
return curr == end;
}

String key = ck(curr, speed);
Boolean val = cache.get(key);
if(val != null) {
return val.booleanValue();
}

boolean flag = s.contains(curr+speed) && canCross(s, end, curr+speed, speed, cache) ||
s.contains(curr+speed+1) && canCross(s, end, curr+speed+1, speed+1, cache) ||
speed > 1 && s.contains(curr+speed-1) && canCross(s, end, curr+speed-1, speed-1, cache);

cache.put(key, flag);
return flag;
}

public boolean canCross(int[] stones) {
Set<Integer> s = new HashSet<>();
for(int n : stones) {