Programming problems which can be solved using recursion

Problem 1: 
There is a terrain on which water flows from West to East. As per laws of Physics, water will flow from higher height to lower height. Find the number of possible paths on which water can flow on the terrain.
The terrain is described by a two-dimensional array A of dimensions M x N.
Each element A[i,j] specifies the height of the point.
Water can only flow from one cell to another cell if one of the following conditions satisfy:
1. A[i][j+1] < A[i][j]
2. A[i-1][j+1] < A[i][j]
3. A[i+1][j+1] < A[i][j]

Input: 
The first line of input will consist of a number N which determines the number of test-cases.
The second line contains two space-separated integers M, N denoting the dimensions of the two-dimensional array.
The next M lines contain N space separated integers each denoting the height of each point A[i,j] of the terrain.

Output:
Output should contain N lines each containing the number of possible paths water can flow from West to East (left-to-right).

Example:

Explanation: 
In the diagram above, there are four paths water can flow from left to right.
1. 10 -> 8 -> 6
2. 10 -> 8 -> 7
3. 12 -> 8 -> 6
4. 12 -> 8 -> 7