How to use Recursion In Javascript
- Create a recursive function that takes a matrix and four variables: k (starting row index), m (ending row index), l (starting column index), and n (ending column index) as the parameters.
- As a base case, the starting index should be less than or equal to the ending index for both rows and columns.
- Now print the boundary elements in a clockwise manner as given in below steps:
- First, print the top row elements. This means print the elements of the k-th row from column index l to n. Then increment the value of k.
- Next, print the right column elements. Print the last column from row index k to m. Then decrease the value of n.
- If k is greater than m, print the bottom row elements. That is, the elements of the (m-1)th row from column n-1 to l and decrement the value of m.
- If l is less than n, print the left column elements of the l-th column from the (m-1)th row to k and increment the value of l.
- Recursively call the function with the updated values of starting and ending indices for rows and columns.
Example: Below is the implementation of the above approach:
Javascript
// JavaScript code for the above approach function printSpiralRecursive(matrix, k, m, l, n) { // Base case if (k > m || l > n) { return '' ; } let result = '' ; // Print the top row from left to right for (let i = l; i <= n; i++) { result += matrix[k][i] + ' ' ; } // Increment the row index from start k++; // Print the right column from top to bottom for (let i = k; i <= m; i++) { result += matrix[i][n] + ' ' ; } // Decrement the column index from end n--; // Check if there is a bottom row to print if (k <= m) { for (let i = n; i >= l; i--) { result += matrix[m][i] + ' ' ; } // Decrement the row index from end m--; } // Check if there is a left column to print if (l <= n) { for (let i = m; i >= k; i--) { result += matrix[i][l] + ' ' ; } // Increment the column index from start l++; } // Recursive Call return result + printSpiralRecursive(matrix, k, m, l, n); } // Function to print the matrix in spiral form function printSpiral(matrix) { const rows = matrix.length; const columns = matrix[0].length; const spiralResult = printSpiralRecursive(matrix, 0, rows - 1, 0, columns - 1); console.log(spiralResult); } // Example const matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9], ]; printSpiral(matrix); |
1 2 3 6 9 8 7 4 5
Time Complexity: O(N*M). To traverse the entire matrix O(N*M) time is required.
Space Complexity: O(1). As we do not use any external data structure here, there is constant space. But obviously the algorithm will consume a recursive stack space of O(n).
JavaScript Program to Print Given Matrix in Spiral Form
Write a JavaScript program to print a given 2D matrix in spiral form.
You are given a two-dimensional matrix of integers. Write a program to traverse the matrix starting from the top-left corner which moves right, bottom, left, and up in a spiral pattern until all the elements are visited. Let us understand it with the examples and figures given below:
Examples:
Example 1:
Input: matrix = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
Output: [1 2 3 6 9 8 7 4 5]
Example 2:
Input: matrix = [[1, 2, 3, 4],
[12, 13, 14, 5],
[11, 16, 15, 6],
[10, 9, 8, 7]]
Output: [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]
Table of Content
- Using Boundary Traversal Approach
- Using Simulation Approach
- Using Recursion in JavaScript
- Using Depth First Search (DFS)