Session 02 Flashcards
Recursion ?
A function that calls itself to solve smaller instances of a problem.
Key elements of recursive function ?
- Base Case (Stopping condition)
- Recursive Case (calling itself with a simpler subproblems)
Structure of recursive function ?
if n == 0: # Base case (termination)
return 1
else: # Recursive case (repetition)
return n * factorial(n-1)Where recustion used?
Mathematical :
* Fibonacci Series
* Factorial Calculation
Searching :
* Binary Search
Sorting :
* Merge Sort
* Quick Sort
Graph & Tree traversals :
* DFS, in-order, pre-order, post-order
Real world applications of Recursion?
- AI - Decision trees & Pathfinding
- Game development - Procedural generation
- Computer graphics - Fractals and Recursive rendering
- Data Structures - Trees and Graphs
Adv & DisAdv of Recursion?
Advantages:
* Simplify code for complex problems
* Mirrors mathematical definitions
* Ideal for devide-and-conquer strategies
Disadvantages :
* Higher memory usage
* Risk of stack overflow
Difference between Recursion and Iteration?
Recursion :
* Termination - Base case
* Memory usage - High (stack frames)
* Performance - Slower
* Readability - Often simpler
Iteration :
* Termination - Condition check
* Memory usage - Low
* Performance - Faster
* Readability - Sometimes complex
Backtracking ?
A systematic trial-and-error approach that eliminates infeasable paths.
Used in :
* Solving puzzles
* Finding optimal paths
Why Backtracking is Efficient?
- Avoids time wasting on impossible solutions.
- Quickly eliminates paths that don’t meet the problem’s conditions, saving both time and computational resources.
Backtracking vs Bruteforce?
Backtracking :
* Explores possibilities only when necessary, pruning invalid choices early.
* More efficient as it avoids unnecessary exploration
* Will find the solution but tries to optimize the process
* Typically use less memory
* Examlpes:
1. N-Queens
2. Sudoku solver
3. Solving mazes
Brute Force :
* Explore every possibilities even those are clearly invalid
* Less efficient, since it doesn’t avoid any paths
* Will find a solution but could be slower
* May require more memory
* Examples :
1. Checking every possible passwords
2. Brute-forcing encryption
3. Searching unsorted data
Example Algorithms of Backtracking?
- Binary Strings : generating all binary strings
- Generating k-ary strings
- The Knapsack problem
- N-Queens problem
- Generalized strings
- Hamiltonian Cycles
- Graph coloring problem
Backtracking vs Recurision?
Recursion :
* Approach - Function call itself
* Purpose - Divide and conquer
* Examples -
1. Factorial
2. Fibonacci
3. Sorting
Backtracking :
* Approach - Tries different possibilities
* Purpose - Optimization
* Examples -
1. N-Queens
2. Sudolu solver
Backtracking & Recursion real world issues?
Recursion :
* Web crawler
* File system traversal
Backtracking :
* Password cracking
* Crossworld puzzle solver
* Image segmentation
