LearnFrenzy
Sign in Take a free test

Methods and Recursion · Predict the Output · Question 19

Counting paths in a grid with recursion Answer, explanation & discussion

  • Output
  • Hard
  • 0 comments
  • Answer explained
  • Moderated community
Question 19 Back to Exercise

What is the output of the following Java program?

Main.java
public class Main {
    // ways to go from (0,0) to (r,c) moving only right or down
    static long paths(int r, int c) {
        if (r == 0 || c == 0) return 1;
        return paths(r - 1, c) + paths(r, c - 1);
    }

    public static void main(String[] args) {
        System.out.println(paths(1, 1) + " " + paths(2, 2) + " " + paths(3, 3) + " " + paths(2, 5));
    }
}
  • A 2 6 20 21 Correct
  • B 2 4 9 10
  • C 1 6 20 21
  • D 2 6 18 21
Correct Answer: Option A

Every path arrives from the cell above or the cell to the left. The counts are binomial coefficients: C(4,2) = 6, C(6,3) = 20, C(7,2) = 21.

Discussion & Comments 0

Share your method, a shortcut, or ask about a step you didn't follow.

No comments yet. Be the first to share your solution!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links