Recursion

What is Recursion?

Recursion is a programming technique where a function calls itself to solve smaller instances of a problem until it reaches a base case (a stopping condition). It's widely used for problems that can be broken down into similar sub-problems.

---

Real-Life Example of Recursion

Example: Russian Dolls (Matryoshka Dolls)

Imagine you have a set of Russian dolls, each nested inside a larger one.

To open all dolls:

• You open the outermost doll.
• Inside, you find another doll and repeat the process.
• You stop when you find the smallest doll, which doesn’t contain any more dolls.

This mimics recursion:

• Recursive Step: Open the next doll (function calls itself).
• Base Case: The smallest doll (no more dolls inside).

---

Tips and Tricks for Solving Problems Using Recursion

1. Identify the Base Case

   • The base case is the simplest version of the problem where recursion will stop.
   • Without a base case, recursion leads to infinite loops or stack overflow.

2. Break Down the Problem

   • Divide the problem into smaller, similar sub-problems.
   • Each recursive call should work on a smaller input.

3. Think in Terms of “What’s Left to Do?”

   • What part of the problem can you handle now, and what can you delegate to future recursive calls?

4. Avoid Redundant Calculations

   • Use memoization or dynamic programming for optimization: store results of sub-problems to avoid re-computation.

5. Understand Stack Limitations

   • Recursive calls use the call stack. Deep recursions can lead to stack overflows. Iterative solutions may be preferred in such cases.

6. Test with Small Inputs

   • Debug your recursion logic with simple and small inputs to verify base case and recursive steps.

---

Must Applicable Conditions for Using Recursion

• Problem Can Be Divided into Similar Sub-Problems: E.g., tree traversal, factorial calculation, Fibonacci sequence.
• Base Case Exists: There is a clear condition to stop further recursive calls.
• Sub-Problems Are Independent: Recursive calls do not interfere with each other’s results.
• Recursive Solution Is More Elegant or Simpler than Iterative: Some problems are naturally recursive (e.g., traversing hierarchical data).

---

Example in Code: Factorial

function factorial(n){
    # Base case
    if n == 0:
        return 1
    # Recursive case
    return n * factorial(n - 1)
}

---

Summary:

Recursion works best when problems are self-similar and have a clear stopping point. Always ensure a base case, break the problem down, and watch out for performance and stack limitations. Use recursion when it makes your code cleaner, simpler, and easier to understand!

Nested category example

const AllCategories = [
  {
    id: 1,
    name: 'Electronics',
    children: [
      {
        id: 2,
        name: 'Mobile Phones',
        children: [
          {
            id: 3,
            name: 'Smartphones',
            children: [],
          },
          {
            id: 4,
            name: 'Feature Phones',
            children: [],
          },
        ],
      },
      {
        id: 5,
        name: 'Laptops',
        children: [],
      },
    ],
  },
  {
    id: 6,
    name: 'Home Appliances',
    children: [],
  },
];

async function processCategory(categories) {
  let result = [];
  for (const category of categories) {
    const product_count=1
    let childrenWithCount=[]
    if(category.children && category.children.length>0){
        childrenWithCount=await processCategory(category.children)
    }
    result.push({ ...category, product_count,children:childrenWithCount });
  }
  return result
}
processCategory(AllCategories)
  .then(result => {
    console.log(JSON.stringify(result));
  })
  .catch(error => {
    console.log(error);
  });

Result

[
  {
    "id": 1,
    "name": "Electronics",
    "children": [
      {
        "id": 2,
        "name": "Mobile Phones",
        "children": [
          {
            "id": 3,
            "name": "Smartphones",
            "children": [],
            "product_count": 1
          },
          {
            "id": 4,
            "name": "Feature Phones",
            "children": [],
            "product_count": 1
          }
        ],
        "product_count": 1
      },
      {
        "id": 5,
        "name": "Laptops",
        "children": [],
        "product_count": 1
      }
    ],
    "product_count": 1
  },
  {
    "id": 6,
    "name": "Home Appliances",
    "children": [],
    "product_count": 1
  }
]