Recursion Concept and Call Stack Visualization in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is recursion in programming?

Recursion is when a function calls itself to solve smaller parts of a problem until it reaches a simple case it can solve directly.

beginner

What is a base case in recursion?

A base case is the simplest situation in recursion where the function stops calling itself to avoid infinite loops.

intermediate

How does the call stack work with recursion?

Each recursive call adds a new layer to the call stack. When a base case is reached, the stack starts to remove layers as functions finish and return results.

intermediate

What happens if a recursive function has no base case?

Without a base case, the function keeps calling itself forever, causing a stack overflow error because the call stack grows too large.

beginner

Explain the flow of a simple factorial function using recursion.

The factorial function calls itself with smaller numbers until it reaches 0 (base case). Then it multiplies the numbers as the calls return, building the final result.

What is the purpose of the base case in a recursive function?

A To stop the recursion and prevent infinite calls

B To call the function again

C To increase the call stack size

D To make the function run faster

The base case stops recursion by providing a simple condition where the function returns without calling itself again.

What happens to the call stack when a recursive function calls itself?

A The stack is cleared

B The stack size decreases

C A new frame is added to the stack for each call

D Nothing changes

Each recursive call adds a new frame to the call stack, storing the function's state until it returns.

Which of these is a correct base case for a factorial function?

A factorial(n) = n + factorial(n - 1)

B factorial(1) = 0

C factorial(n) = n * factorial(n + 1)

D factorial(0) = 1

The factorial of 0 is defined as 1, which is the base case stopping recursion.

What error occurs if a recursive function never reaches a base case?

A Syntax error

B Stack overflow error

C Type error

D Memory leak

Without a base case, recursion never stops, causing the call stack to overflow.

In recursion, what does 'unwinding the call stack' mean?

A Returning from recursive calls one by one

B Adding new calls to the stack

C Clearing all variables

D Starting recursion again

Unwinding means the function returns from each recursive call, removing frames from the call stack.

Describe how recursion uses the call stack to solve problems step-by-step.

Think about how each call waits for the next before finishing.

Explain why a base case is essential in recursion and what happens if it is missing.

Consider what would happen if the function never stops calling itself.