Search code examples
algorithmrecursionmatrixpseudocodepath-finding

How do i show the recursion process for these steps in simple Pseducode?


I'm not sure how to convert these steps to Pseducode. How do i show the recursion process for these steps in simple Pseducode?

Input: Matrix (n,m)

Output: all valid paths to cell (n, m)

  1. start at (1,1) move to the right cell and again choose one of the possible moves ( right or down ) and repeat these steps till we reach (n,m).

  2. start at (1,1) move to the the cell below and again choose one of the possible moves ( right or down ) and repeat these steps till we reach (n,m) So from each cell first return all paths by going down and then return all paths by going right. Do this recursively for each cell encountered.

  3. return paths and paths sum from (1,1) to (n,m)


Solution

  • C[i,j]=C[1,1]; for 0 < i < n , 0 < j < m
    C[i,j] move to C[i,j+1]
    choose C[i,j+2] or C[i+1,j+1]
    repeat these steps till we reach C[n,m]
    C[i,j] move to C[i+1,j]
    choose C[i+2,j] or C[i+1,j+1]
    repeat these steps till we reach C[n,m]
    find sum for each path from C[1,1] to C[n,m]
    return all paths from C[1,1] to C[n,m]
    return all path sums from C[1,1] to C[n,m]