Why Recursion Exists and What Loops Cannot Express Cleanly in DSA Typescript - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Factorial Function

What is the output of the following TypeScript code that uses recursion to calculate factorial?

DSA Typescript

function factorial(n: number): number {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(4));

A 120

B 10

C 24

D 6

💡 Hint

Think about how factorial multiplies numbers from n down to 1.

The factorial of 4 is 4 * 3 * 2 * 1 = 24. The recursive function multiplies n by factorial(n-1) until n is 1.

🧠 Conceptual

intermediate

Why Recursion Can Express Tree Traversals More Cleanly Than Loops

Why is recursion often preferred over loops when traversing tree structures?

A Recursion naturally handles branching by calling itself for each child, while loops require manual stack management.

B Loops are faster than recursion for trees, so recursion is avoided.

C Recursion cannot be used for trees because it causes infinite loops.

D Loops automatically traverse all nodes without extra code.

💡 Hint

Think about how trees have multiple branches and how recursion calls itself for each branch.

Recursion fits tree traversal because each recursive call can handle one branch, making code simpler. Loops need extra data structures to track nodes.

🔧 Debug

advanced

Identify the Error in Recursive Fibonacci Implementation

What error does the following TypeScript code produce when run?

DSA Typescript

function fib(n: number): number {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fib(n - 1) + fib(n - 2);
}
console.log(fib(-1));

A Stack overflow error due to infinite recursion

B Returns 0 without error

C Returns 1 without error

D Syntax error

💡 Hint

Consider what happens when n is negative in the recursive calls.

The function does not handle negative inputs, so calls keep decreasing n indefinitely, causing infinite recursion and stack overflow.

🚀 Application

advanced

Using Recursion to Flatten Nested Arrays

Which option correctly outputs the flattened array from a nested array using recursion in TypeScript?

DSA Typescript

const nested = [1, [2, [3, 4], 5], 6];
function flatten(arr: any[]): number[] {
  let result: number[] = [];
  for (const el of arr) {
    if (Array.isArray(el)) {
      result = result.concat(flatten(el));
    } else {
      result.push(el);
    }
  }
  return result;
}
console.log(flatten(nested));

A [1, 2, [3, 4], 5, 6]

B [1, [2, [3, 4], 5], 6]

C [[1, 2, 3, 4, 5, 6]]

D [1, 2, 3, 4, 5, 6]

💡 Hint

Flattening means removing all nested arrays and putting all elements in one list.

The recursive function checks if an element is an array; if yes, it flattens it recursively, else it adds the element to the result.

🧠 Conceptual

expert

Why Some Problems Cannot Be Cleanly Solved Using Loops Alone

Which statement best explains why recursion is necessary for some problems instead of just using loops?

A Loops are always slower and less memory efficient than recursion.

B Some problems have self-similar structures that require the function to call itself with smaller inputs, which loops cannot express naturally.

C Loops cannot be nested, so they cannot handle complex problems.

D Recursion uses less code but cannot solve problems loops can.

💡 Hint

Think about problems like tree traversals or divide-and-conquer algorithms.

Recursion matches problems where the solution depends on smaller versions of the same problem, which loops cannot express without extra data structures.