Recursion

Recursion / DFS / Backtracking

Recursion

• Solving a large problem by depending on solutions to smaller subproblems

• Three Elements of Recursion

  • Definition
  • Base Case
  • Breakdown

Depth-First Search (DFS)

• Can be implemented using recursive functions.
• Can also be implemented without recursion, using a manually created stack (like stack) for operations.
• DFS prioritizes exploring deeper nodes during search rather than breadth-first search (BFS) across the same level of nodes.

Backtracking

• Backtracking is essentially the same as Depth-First Search (DFS).
• Backtracking Operation: When a recursive function returns to the previous level of recursion, some parameters need to revert to their values before the call. This operation, known as backtracking, resets state parameters to their previous values, undoing changes made before the recursive call.

Traversal vs. Divide-and-Conquer

Traversal

• Imagine a person with a notebook visiting all nodes.
• Often involves a global variable or shared parameter.

Divide-and-Conquer

• Assigning subtasks to others while summarizing results.
• Typically uses return values to record results from subproblems.
• Divide-and-conquer on a binary tree essentially performs post-order traversal.

Backtracking

• 3 main components
  • choice: decisions to make in each step
  • constraints: your decision is restricted somehow
  • goal: eventually converge to a goal

Depth-First Search (DFS)

• Starting from a point, choose any path to the next point, continuing until reaching an endpoint. If reaching an endpoint, backtrack one step and try another path.
• During traversal, search for a target value or path.
• Avoid revisiting nodes within the same path, but nodes visited in different paths may be revisited.
• In general, unless specifically required otherwise, DFS is commonly implemented using recursion.

Complexity of BFS vs. DFS

• Both have a time complexity of O(V + E), where V is the number of vertices and E is the number of edges.

• BFS (Breadth-First Search) space complexity depends on the breadth.

• DFS (Depth-First Search) space complexity depends on the depth.

When to Use DFS?

• problems involving binary trees can be solved using DFS.
• Apart from binary trees, about 90% of DFS problems involve combinations or permutations.
  • Problems requiring finding all solutions often use DFS.
  • If a problem provides a tree or graph, DFS can be applied directly on it.
  • If not directly given a tree or graph, consider the problem’s solution space as a tree or graph and apply DFS to find all valid paths or solutions.

Backtracking v.s. DFS

• Backtracking is something that happens during search, but it also refers to a specific problem-solving technique where a lot of backtracking is done. src 
  • The more specific usage refers to a problem-solving strategy that is similar to depth-first search but backtracks when it realizes that it’s not worth continuing down some subtree.
  • a naive DFS blindly visits each node until it reaches the goal. Yes, it “backtracks” on leaf nodes. But a backtracker also backtracks on useless branches.
• Backtracking is DFS for implicit tree, while DFS is backtracking without pruning. src 
  • When the search space of a problem is visited by backtracking,the implicit tree gets traversed and pruned in the middle of it.
  • Yet for DFS, the tree/graph it deals with is explicitly constructed and unacceptable cases have already been thrown, i.e. pruned, away before any search is done.