Scribd
Upload
4 views25 pages

Recursion Slides

The document provides an overview of recursion, defining it as a technique where a function calls itself to solve problems, and outlines its key components including base and recursive cases. It discusses various types of recursion, the importance of analyzing recursive algorithms for time and space complexity, and strategies for writing and debugging recursive functions. Additionally, it compares recursion with iteration and highlights common errors and best practices in using recursion.

Uploaded by

misbah jamil
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views25 pages

Recursion Slides

The document provides an overview of recursion, defining it as a technique where a function calls itself to solve problems, and outlines its key components including base and recursive cases. It discusses various types of recursion, the importance of analyzing recursive algorithms for time and space complexity, and strategies for writing and debugging recursive functions. Additionally, it compares recursion with iteration and highlights common errors and best practices in using recursion.

Uploaded by

misbah jamil
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Recursion & Analysis

• Beginner to Advanced Level


• Data Structures & Algorithms
What is Recursion?
Definition:
Recursion is a technique where a function calls
itself to solve a problem.
Core idea:
• Solve a smaller version of the same problem
Real-Life Analogy

• Mirror reflecting mirror (infinite reflections)


• Russian dolls (nested structure)
• Tree branches splitting into smaller branches
Key Components of Recursion

Every recursive function must have:


Base Case
→ Stops recursion
Recursive Case
→ Function calls itself
How Recursion Works Internally
• Uses Call Stack
• Each call:
– Stores parameters
– Waits for result
Simple Example (Factorial)

Step-by-Step Execution (fact(4))


Call Stack Concept
• Each recursive call is stored in stack memory
• Stack grows until base case is reached
• Then it unwinds
Important
• Recursion behavior is tied to runtime stack
execution
Visual Stack Trace
Types of Recursion
• Direct Recursion
• Indirect Recursion
• Tail Recursion
• Non-Tail Recursion
• Nested Recursion
Direct Recursion

Function calls itself directly:


Indirect Recursion

Functions call each other:


Tail Recursion (Important)

• Recursive call is the last operation

1. Efficient
2. Can be converted to loop
Non-Tail Recursion

Work remains after recursive call


Uses more stack
Nested Recursion

Very complex
Rarely used
RECURSION DESIGN STRATEGY
How to Write Recursive Function
Step-by-step:
1. Identify base case
2. Break problem into smaller part
3. Call function recursively
4. Combine results
Example – Sum of n numbers
Debugging Recursion

Trace with small inputs


Draw recursion tree
Check base case carefully
ANALYSIS OF RECURSIVE ALGORITHMS
Why Analyze?
To measure:
• Time Complexity
• Space Complexity
Recurrence Relation
• Used to represent recursive time complexity
• Example:
T(n) = T(n-1) + c
Solving Recurrence (Step-by-Step)
Given:
T(n) = T(n-1) + c
Expand:
= T(n-2) + 2c
= T(n-3) + 3c
...
= T(1) + (n-1)c
Final:
T(n) = O(n)
Recursion Tree Method
Example:
T(n) = 2T(n/2) + n
Tree:
Level 0: n
Level 1: n
Level 2: n
...

Total:
O(n log n)
Space Complexity

Depends on recursion depth:


Algorithm Space
Factorial O(n)
Binary Search O(log n)
Backtracking

• Uses recursion to explore all possibilities


• Example:
– N-Queens
– Maze solving
Divide & Conquer

Steps:
• Divide
• Conquer
• Combine
Examples:
• Merge Sort
• Quick Sort
Recursion vs Iteration

Recursion Iteration
Elegant Faster
Uses stack Uses loops
Easy for trees Harder for trees
Common Errors &Best Practices
Missing base case
Infinite recursion
Stack overflow
Incorrect recurrence
Best Practices
Always define base case first
Keep recursion simple
Analyze complexity early
Convert to iteration if needed

You might also like