Data Structures & Algorithms Notes Page

Recursion:

What is Recursion?

• Recursion is when a function calls itself in order to solve a smaller instance of a problem.

Structure of a Recursive Function:

• A recursive function has:
  1. Base Case: A condition that stops the function.
  2. Recursive Case: A part where the function calls itself with a modified input.

Example:

def factorial(n)
	if (n == 0)   // Base Case
		return 1;
		
	else          // Recursive Case
		return n * factorial(n - 1);

When Not To Use Recursion

Performance Issues:

• Recursion can lead to high memory use due to call stack.

Stack Overflow:

• Too many recursive calls can cause the stack to overflow if there is no proper base case.

Efficiency:

• Iterative solutions are often more efficient for simple problems.