Scribd
Upload
2 views2 pages

Recursion and Stacks Notes

Recursion is a programming technique where a function calls itself to solve problems, using base and recursive cases. It utilizes a stack data structure to manage function calls and local variables, which can lead to advantages like simplified code but also disadvantages such as increased memory usage and potential stack overflow. The document also contrasts recursion with iteration, noting that while recursion is often easier to implement, iteration is generally more memory-efficient.

Uploaded by

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

Recursion and Stacks Notes

Recursion is a programming technique where a function calls itself to solve problems, using base and recursive cases. It utilizes a stack data structure to manage function calls and local variables, which can lead to advantages like simplified code but also disadvantages such as increased memory usage and potential stack overflow. The document also contrasts recursion with iteration, noting that while recursion is often easier to implement, iteration is generally more memory-efficient.

Uploaded by

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

Recursion and Its Relation with Stacks

1. Introduction to Recursion
Recursion is a programming technique where a function calls itself to solve a problem. It is
mainly used to break complex problems into smaller subproblems of the same type.

2. Key Concepts of Recursion


• Base Case: The condition where recursion stops.
• Recursive Case: The part where the function calls itself.
• Recursive Function: A function that calls itself.

3. Example of Recursion (Factorial)


Factorial of n (n!) is defined as:
n! = n × (n-1)!
Base Case: 0! = 1

Pseudo Code:
function factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)

4. What is a Stack?
A stack is a linear data structure that follows the LIFO (Last In First Out) principle.
Operations include push (insert) and pop (remove).

5. Relation Between Recursion and Stack


Recursion internally uses a stack data structure called the call stack.

• Each recursive call is pushed onto the stack.


• When a function completes, it is popped from the stack.
• The stack stores function parameters, local variables, and return addresses.
6. Working of Recursion Using Stack (Factorial Example)
For factorial(3):
Step 1: factorial(3) → waits for factorial(2)
Step 2: factorial(2) → waits for factorial(1)
Step 3: factorial(1) → waits for factorial(0)
Step 4: factorial(0) returns 1

Now stack unwinds:


factorial(1) = 1 × 1 = 1
factorial(2) = 2 × 1 = 2
factorial(3) = 3 × 2 = 6

7. Advantages of Recursion
• Simplifies code
• Suitable for problems like tree traversal, factorial, Fibonacci
• Reduces complexity for divide-and-conquer problems

8. Disadvantages of Recursion
• Uses more memory due to stack calls
• Can lead to stack overflow if not handled properly
• Sometimes slower than iterative solutions

9. Recursion vs Iteration
Recursion uses function calls and stack memory, while iteration uses loops.
Recursion is easier to write but may consume more memory.
Iteration is more efficient in terms of memory.

You might also like