Yang Hui’s Triangle (Pascal’s Triangle) is a special triangular arrangement of numbers used in many areas of mathematics.

/ Exams & Certification / By

Yang Hui’s Triangle (Pascal’s Triangle) is a special triangular arrangement of numbers used in many areas of mathematics. The following diagram shows the first 8 rows of the triangle. Each number is the sum of the top two numbers. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 Write a recursive function yanghui(n,m), which returns the value on the position nth row and mth column. In the submission, you should use the test case for (n,m) as (5,3) and (8,5), the results should be respectively 6 and 35. (Don’t use nested for loop, there will be no credit using previous solution).

The Correct Answer and Explanation is:

To solve this problem, you need to create a recursive function yanghui(n, m) that returns the value in the nth row and mth column of Yang Hui’s Triangle (also known as Pascal’s Triangle).

Key Idea:

In Pascal’s Triangle, each number is the sum of the two numbers directly above it. Specifically, the element at position (n, m) (n-th row, m-th column) is the sum of the element at (n-1, m-1) and (n-1, m).

Recursive Formula:

  • The recursive function should return 1 when either m == 1 or m == n (because the edges of Pascal’s Triangle are always 1).
  • Otherwise, it should return the sum of two elements:
    • The element above-left: yanghui(n-1, m-1)
    • The element above-right: yanghui(n-1, m)

This approach ensures that you build up the triangle from the top down.

Recursive Function Definition:

pythonCopyEditdef yanghui(n, m):
    # Base case: when m is at the edge of the row (first or last element)
    if m == 1 or m == n:
        return 1
    # Recursive case: calculate sum of two elements above
    return yanghui(n - 1, m - 1) + yanghui(n - 1, m)

Explanation:

  • Base Case: If m == 1 or m == n, we return 1 because the first and last elements of each row are always 1 in Pascal’s Triangle.
  • Recursive Case: For any other position, the value is the sum of the two values directly above it. Hence, the recursive calls are made to yanghui(n - 1, m - 1) and yanghui(n - 1, m) to compute the sum.

Test Cases:

Let’s use the test cases provided: (5, 3) and (8, 5).

Test Case 1: (5, 3)

This corresponds to the 5th row and 3rd column in Pascal’s Triangle:

yamlCopyEditRow 5: 1  4  6  4  1
       Index:  1  2  3  4  5

For (5, 3), we want the 3rd element in the 5th row, which is 6. The recursive calls would work as follows:

  • yanghui(5, 3) is yanghui(4, 2) + yanghui(4, 3)
  • yanghui(4, 2) is yanghui(3, 1) + yanghui(3, 2)
  • yanghui(3, 1) is 1 (base case)
  • yanghui(3, 2) is 2 (recursive case)
  • yanghui(4, 3) is yanghui(3, 2) + yanghui(3, 3)
  • yanghui(3, 3) is 1 (base case)

This results in 6.

Test Case 2: (8, 5)

This corresponds to the 8th row and 5th column:

yamlCopyEditRow 8: 1  7  21  35  35  21  7  1
       Index:  1  2  3  4  5  6  7  8

For (8, 5), we want the 5th element in the 8th row, which is 35. The recursive calls would work similarly, eventually summing the values that give 35.

Recursion Example for (5, 3):

  1. Call yanghui(5, 3)
    • Calls yanghui(4, 2) and yanghui(4, 3)
  2. Call yanghui(4, 2)
    • Calls yanghui(3, 1) and yanghui(3, 2)
  3. Call yanghui(3, 1) returns 1 (base case)
  4. Call yanghui(3, 2)
    • Calls yanghui(2, 1) and yanghui(2, 2)
  5. Call yanghui(2, 1) returns 1 (base case)
  6. Call yanghui(2, 2) returns 1 (base case)

Eventually, the result is 6.

Conclusion:

This recursive function efficiently calculates any element in Pascal’s Triangle by breaking down the problem into smaller subproblems, based on the triangle’s recursive nature. The base case ensures proper stopping conditions, and the recursive calls allow the function to build the values up row by row

Related Posts

Scroll to Top