Recursion
Published: 2023-10-20 14:57:16

- What is recursion?

Recursion is a concept in coding that involves a function repeatedly calling itself to perform a given action. There are two key elements to every recursive function: the base case and the recursive case. The base case denotes when the recursion should stop, which serves to prevent endless loops. The recursive case dictates how the function calls itself. It modifies the inputs until they become closer to the base case. The first function call uses the original input, and the result is determined by combining results from recursive calls.

- What can recursion be used for?

Recursion is commonly used for tasks such as iterating through data structures and solving problems that can be divided into smaller sub-problems.They can be used to traverse arrays, lists, trees, or other hierarchal data structures. It can also be used if one needs to check for something multiple times in the same function call.

Here's one example for logging an array using a recursive function. It will delete the first element of the array in each call and stop when the array is empty.

```
const myArray = [1, 2, 3, 4, 5]; // array to iterate through
function recursive(arr) {
  if (arr.length === 0) {
    return; /// base case
  }
  console.log(arr[0]) // logs the first element of the array
  recursiveSplice(arr.slice(1)) // calls itself again with the element that was logged removed from the array.
}
recursive(myArray) ///Logs each element
```

- How can it be applied in a program?
Imagine you're making a match 3 game, such as Candy Crush. You might implement a recursive function in order to check if  a game object is touching two others of its kind and remove them, granting the player points. 

```
const gameBoard = [
  [1, 1, 3, 2, 3],
  [3, 1, 2, 1, 3],
  [3, 1, 3, 2, 2],
  [1, 3, 1, 1, 3],
  [2, 2, 3, 2, 1]
]
```
 This is A board containing pieces to iterate through. The 1s in the 2nd column are matching, so they should be removed.
```
function checkMatches(board, row, col, value, visited) {
  if (
    row < 0 ||
    row >= board.length || // makes sure the index stays inside the board vertically
    col < 0 ||
    col >= board[row].length //Makes sure not to check outside the board horizontally || 
    visited[row][col] //Makes sure not to check already visited places ||
    board[row][col] !== value //Doesn't count it if the sector doesn't match the given value
  ) {
    return; //Stops the function
  }
```
this code returns the base case if any of the conditions are met on the call.

```
  visited[row][col] = true;
  let count = 1; //Marks the area we're currently at as visited and counts it as one
```
marks the default area as visited so there's no confusion as we check the areas surrounding it.
```
  // Recursively check horizontally and vertically
  count += checkAndRemoveMatches(board, row - 1, col, value, visited); // Up
  count += checkAndRemoveMatches(board, row + 1, col, value, visited); // Down
  count += checkAndRemoveMatches(board, row, col - 1, value, visited); // Left
  count += checkAndRemoveMatches(board, row, col + 1, value, visited); // Right

```
This is the recursive case where we check around an object for each direction and call the function again on those elements, and add to the count if they return true. This creates a kind of branching function that continues to check for matches in the same direction.
``` 
  // If we've found a match, remove the item
  if (count >= 3) {
    board[row][col] = 0; // zeroes are removed by a different function and points are added
  }

  return count; // return the number of the same number that are connected.
}
```
Finally, if the count is 3 or more, we remove all the elements that are touching similar elements and give the player points. Another function would replace these 0s with new, random elements.
``` 

 for (let row = 0; row < numRows; row++) {
    for (let col = 0; col < numCols; col++) {
        checkAndRemoveMatches(board, row, col, board[row][col], visited);
    }
  } //This should find the 3 lined up 1s and replace them with 0s
```
This is how we would call the function on the game board in order to make sure we check every element in it.



In conclusion, recursion can be an extremely useful tool for both iteration and other traversal of data in coding. It's one of the most important things to learn to adapt to, because it's the answer to a lot of problems one might have with their code.