The purpose of this assignment is to give you practice writing programs with recursion.


  1. Delannoy numbers (brute force). Write a program DelannoyBrute.java that takes two integer command-line arguments m and n and computes the corresponding Delannoy number. The Delannoy number \( D(m, n)\) is the number of paths from \((0, 0)\) to \((m, n)\) in a rectangular grid using only single steps north, east, and northeast. For example, \(D(2, 2) = 13\) because there are 13 possible Delannoy paths:


    13 possible Delannoy paths in a 2-by-2 grid


    Implement a recursive function count() to compute \( D(m, n)\) by using the following recurrence relation:

    \( \displaystyle D(m, n) \; = \; \begin{cases} \;\; 1 & \text{if } m = 0 \\[.5em] \;\; 1 & \text{if } n = 0 \\[.5em] \;\; D(m-1, n) + D(m-1, n-1) + D(m, n-1) & \text{otherwise} \end{cases} \)

    To do so, organize your program according to the following public API: 

    public class DelannoyBrute {

    // Returns the Delannoy number D(m, n).
    public static long count(int m, int n)

    // Takes two integer command-line arguments m and n and prints D(m, n).
    public static void main(String[] args)
}

    As you will see, this approach is hopelessly slow, even for moderately large values of m and n. 

    ~/Desktop/recursion> java-introcs DelannoyBrute 2 2
13

~/Desktop/recursion> java-introcs DelannoyBrute 3 2
25

~/Desktop/recursion> java-introcs DelannoyBrute 2 3
25

~/Desktop/recursion> java-introcs DelannoyBrute 3 3
63

~/Desktop/recursion> java-introcs DelannoyBrute 20 20
[takes too long]

    Note: you may assume that m and n are non-negative integers.

    Delannoy numbers arise in combinatorics and computational biology. For example, \(D(m, n)\) is the number of global alignments of two strings of lengths m and n.


  2. Delannoy numbers (dynamic programming). Write a program DelannoyDP.java that takes two integer command-line arguments m and n and computes the Delannoy number \(D(m, n)\) using dynamic programming. Hint: use a two-dimensional array with element delannoy[i][j] storing \(D(i, j)\).

    To do so, organize your program according to the following public API: 

    public class DelannoyDP {

    // Returns the Delannoy number D(m, n).
    public static long count(int m, int n)

    // Takes two integer command-line arguments m and n and prints D(m, n).
    public static void main(String[] args)
}
    This version should be fast enough to handle larger values of m and n. 
    ~/Desktop/recursion> java-introcs DelannoyDP 2 2
13

~/Desktop/recursion> java-introcs DelannoyDP 3 2
25

~/Desktop/recursion> java-introcs DelannoyDP 2 3
25

~/Desktop/recursion> java-introcs DelannoyDP 3 3
63

~/Desktop/recursion> java-introcs DelannoyDP 20 20
260543813797441