DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
ALGORITHMIC THINKING WITH PYTHON
Prof. Sarju S
26 November 2024
Module 3
Page 2
Module 3
► SELECTION AND ITERATION USING PYTHON:- if-else, elif, for loop, range, while loop.
► SEQUENCE DATA TYPES IN PYTHON - list, tuple, set, strings, dictionary, Creating and
using Arrays in Python (using Numpy library).
► DECOMPOSITION AND MODULARIZATION* :- Problem decomposition as a strategy for
solving complex problems, Modularization, Motivation for modularization, Defining and
using functions in Python, Functions with multiple return values
► RECURSION:- Recursion Defined, Reasons for using Recursion, The Call Stack,
Recursion and the Stack, Avoiding Circularity in Recursion, Sample problems - Finding
the nth Fibonacci number, greatest common divisor of two positive integers, the
factorial of a positive integer, adding two positive integers, the sum of digits of a
positive number **.
Page 3 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Recursion
Page 4
What is Recursion?
► Recursion is a programming technique where a function calls itself to solve a smaller
instance of the same problem.
► This process continues until the problem is reduced to a base case—a condition where
the recursion stops.
Page 5 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
What is Recursion?
► Imagine that you are in a queue of people and you want to know how many people
were in front of you?
Page 6 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
What is Recursion?
Hey,
How many people
are in font of you?
Page 7 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
What is Recursion?
Hey,
How many people
are in font of you?
Page 8 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
What is Recursion?
Hey,
How many people
are in font of you?
Page 9 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
What is Recursion?
Page 10 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
What is Recursion?
Page 11 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
What is Recursion?
Page 12 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
What is Recursion?
Page 13 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Anatomy of a Recursive Function
► A recursive function generally has the following structure:
► Base Case: A condition to stop the recursion and prevent infinite calls.
► Recursive Case: A smaller version of the same problem, leading toward the base case.
def recursive_function(param): def factorial(n):
if base_case_condition: # Base case if n == 1: # Base case
return result return 1
else: else:
# Recursive case # Recursive call
return recursive_function(smaller_param) return n * factorial(n - 1)
Page 14 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Key Components of Recursion
► Base Case: The base case is critical as it ensures that the recursion
terminates.
► Without it, the function will keep calling itself indefinitely, causing a stack
overflow.
def countdown(n):
if n == 0: # Base case
print("Blastoff!")
else:
print(n)
countdown(n - 1) # Recursive call
Page 15 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Key Components of Recursion
► Progress Toward the Base Case: Each recursive call must reduce the size or
complexity of the problem, moving it closer to the base case.
def sum_numbers(n):
if n == 0: # Base case
return 0
else:
return n + sum_numbers(n - 1) # Progressing towards base case
Page 16 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
The Call Stack
► A stack is a data structure that follows the LIFO (Last In, First Out) principle
► The last item added to the stack is the first item removed.
► Push 10 → Stack: [10]
► Push 20 → Stack: [10, 20]
► Pop → Removes 20 → Stack: [10]
Page 17 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
The Call Stack
► The call stack is a special data structure used by programs to manage
function calls. Whenever a function is called:
► The current state of the function (execution context) is pushed onto the call stack.
► The recursive call creates a new instance of the function, which is also pushed onto the
stack.
► When the base case is reached, the stack begins to unwind, resolving each function call
in reverse order.
Page 18 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
How the Stack Works in Recursion
def factorial(n):
if n == 1: # Base case
return 1
else:
return n * factorial(n - 1) # Recursive call
Let’s compute 3! using recursion:
Page 19 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
How the Stack Works in Recursion
Page 20 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
How the Stack Works in Recursion
Page 21 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
How the Stack Works in Recursion
Page 22 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
How the Stack Works in Recursion
Page 23 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
How the Stack Works in Recursion
Page 24 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Recursion tree for 4!.
► In the tree diagram:
► Each node represents a call to the
factorial function.
► The children of each node
represent the recursive calls made
by that function.
► The return values are shown next to
each node to illustrate the result of
the recursive call.
► the multiplication operations are
indicated to show how each result
is computed.
Page 25 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Avoiding Circularity in Recursion
► Circularity in recursion occurs when the function lacks a clear base case or
fails to progress toward it, leading to infinite recursive calls and eventual
stack overflow.
► To avoid circularity:
► Always Define a Base Case: Ensure there's a condition to terminate recursion. For
example, in a factorial function, the base case is when n == 1.
► Progress Toward the Base Case: Ensure that each recursive call moves the problem
closer to the base case. For instance, decrementing n in factorial(n - 1) ensures
progress.
► Test Your Function Thoroughly: Check edge cases to verify that the base case is
reached under all conditions.
Page 26 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Avoiding Circularity in Recursion
def bad_recursion(n):
print(n)
bad_recursion(n) # No base case, leads to infinite recursion.
def good_recursion(n):
if n == 0: # Base case
print("Done!")
else:
print(n)
good_recursion(n - 1) # Moves closer to the base case.
Page 27 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Exercises
► Finding the Maximum Element in a List
► Example Input: [1, 3, 5, 2, 4]
► Example Output: 5
► Solution Steps
1. Understand the Problem: Identify the largest number in the list.
2. Identify the Base Case: If the list has only one element, that element is the maximum.
3. Define the Recursive Case: The maximum of a list is the greater of the first element and
the maximum of the rest of the list.
4. Implement the Recursive Function
5. Test the Recursive Function
Page 28 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Exercises
► Finding the Maximum Element in a List
► Example Input: [1, 3, 5, 2, 4]
► Example Output: 5
def find_max_recursive(numbers):
if len(numbers) == 1:
return numbers[0]
else:
max_of_rest = find_max_recursive(numbers[1:])
return numbers[0] if numbers[0] > max_of_rest else max_of_rest
numbers = [3, 1, 4, 1, 5]
print("The maximum element is:", find_max_recursive(numbers))
Page 29 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Exercises
def find_max_recursive(numbers):
if len(numbers) == 1:
return numbers[0]
else:
max_of_rest = find_max_recursive(numbers[1:])
return numbers[0] if numbers[0] > max_of_rest else max_of_rest
numbers = [3, 1, 4, 1, 5]
print("The maximum element is:", find_max_recursive(numbers))
Step Call Stack Action
Step 1 (Initial) find_max_recursive([3, 1, 4, 1, 5]) Calls itself with [1, 4, 1, 5].
Step 2 find_max_recursive([1, 4, 1, 5]) Calls itself with [4, 1, 5].
Step 3 find_max_recursive([4, 1, 5]) Calls itself with [1, 5].
Step 4 find_max_recursive([1, 5]) Calls itself with [5].
Step 5 (Base Case) find_max_recursive([5]) Returns 5.
Step 4 Resolves: max(1, 5) = 5. Returns 5.
Step 3 Resolves: max(4, 5) = 5. Returns 5.
Step 2 Resolves: max(1, 5) = 5. Returns 5.
Step 1 Resolves: max(3, 5) = 5. Returns 5.
Page 30 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Reversing a String
def reverse_string_recursive(s):
# Base case: If the string is empty or has one character, it is already reversed
if len(s) <= 1:
return s
else:
# Recursive case: Reverse the rest of the string and append the first character
return reverse_string_recursive(s[1:]) + s[0]
# Example usage
input_string = "recursion"
reversed_string = reverse_string_recursive(input_string)
print("Original String:", input_string)
print("Reversed String:", reversed_string)
Page 31 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Reversing a String
def reverse_string_recursive(s):
# Base case: If the string is empty or has one character, it is already reversed
if len(s) <= 1:
return s
else:
# Recursive case: Reverse the rest of the string and append the first character
return reverse_string_recursive(s[1:]) + s[0]
Step Call Stack Action
Step 1 (Initial) reverse_string_recursive("recursion") Calls itself with "ecursion".
Step 2 reverse_string_recursive("ecursion") Calls itself with "cursion".
Step 3 reverse_string_recursive("cursion") Calls itself with "ursion".
... ... ...
Base Case reverse_string_recursive("n") Returns "n".
Step n-1 Resolves: "n" + "o" = "no". Returns "no".
Step n-2 Resolves: "no" + "i" = "noi". Returns "noi".
Final Step Resolves: "noisrucer" + "r". Returns "noisrucer".
Page 32 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Counting the Occurrences of a Value in a List
def count_occurrences(lst, value):
if not lst: # Base case: empty list
return 0
count = 1 if lst[0] == value else 0
return count + count_occurrences(lst[1:], value)
# Example usage
numbers = [1, 2, 3, 2, 4, 2, 5]
target_value = 2
count = count_occurrences(numbers, target_value)
print(f"The value {target_value} appears {count} times in the list.")
Page 33 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Counting the Occurrences of a Value in a List
lst[0] == Returned
Call Level Function Call lst Count
value Value
count_occurrences([1, 2, 3, 2, 4, 2],
1 [1, 2, 3, 2, 4, 2] False 0
2)
2 count_occurrences([2, 3, 2, 4, 2], 2) [2, 3, 2, 4, 2] True 1
3 count_occurrences([3, 2, 4, 2], 2) [3, 2, 4, 2] False 0
4 count_occurrences([2, 4, 2], 2) [2, 4, 2] True 1
5 count_occurrences([4, 2], 2) [4, 2] False 0
6 count_occurrences([2], 2) [2] True 1
7
count_occurrences([], 2) [] - 0 0
(Base Case)
Page 34 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Counting the Occurrences of a Value in a List
Call Level Function Call Count Value Returned
7 (Base Case) count_occurrences([], 2) 0 0
6 count_occurrences([2], 2) 1 1+0=1
5 count_occurrences([4, 2], 2) 0 0+1=1
4 count_occurrences([2, 4, 2], 2) 1 1+1=2
3 count_occurrences([3, 2, 4, 2], 2) 0 0+2=2
2 count_occurrences([2, 3, 2, 4, 2], 2) 1 1+2=3
1 count_occurrences([1, 2, 3, 2, 4, 2], 2) 0 0+3=3
Page 35 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Difference Between Iteration and Recursion
Aspect Iteration Recursion
Calls a function repeatedly,
Repeats a block of code using
Definition where the function calls itself
loops (e.g., for, while).
with modified parameters.
Iterative approach with control Recursive approach with
Approach
structures like loops. function calls and base cases.
Requires variables to store and
State is implicitly managed by
State Management update state explicitly (e.g.,
the call stack.
counters).
Loop exits when a condition is Recursion stops when a base
Termination Condition
satisfied. case is reached.
More memory usage due to
Efficient memory usage as no
Memory Usage stack frames for each recursive
extra stack frames are created.
call.
Generally faster as it avoids the Slightly slower due to the
Performance overhead of multiple function overhead of maintaining stack
calls. frames.
Page 36 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Difference Between Iteration and Recursion
Aspect Iteration Recursion
Clear for simple iterations but More concise and elegant for
Readability may become complex for nested problems like tree traversal or
loops. divide-and-conquer.
More prone to errors like stack
Easier to debug with fewer
Debugging overflow or infinite recursion
potential errors.
without a base case.
Suitable for problems that can be
Suitable for tasks involving
broken into smaller subproblems
Suitability simple, repeated actions (e.g.,
(e.g., factorial, Fibonacci, tree
iterating over a list).
traversal).
Page 37 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Reasons for using Recursion
► Simplifies Complex Problems
► Some problems are naturally recursive, meaning they are easier to break down into smaller
subproblems of the same type (e.g., traversing trees, solving mazes, etc.).
► Example: Calculating factorial, navigating hierarchical data (e.g., file systems).
► Reduces Code Complexity
► Recursive solutions often require fewer lines of code compared to iterative solutions, making the
logic easier to understand and maintain.
► A recursive Fibonacci sequence implementation is much shorter than its iterative counterpart.
► Better Representation for Divide and Conquer Algorithms
► Algorithms like Merge Sort, Quick Sort, and Binary Search are naturally expressed using recursion
since they divide the problem into smaller subproblems.
Page 38 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Reasons for using Recursion
► Processes Dynamic Structures
► Data structures like trees and graphs are easier to process using recursion because their structure
is hierarchical and self-referential.
► Example: Traversing a binary tree (e.g., pre-order, in-order, or post-order traversal).
► Handles Infinite or Unknown Sizes
► In scenarios where the size of the problem isn't fixed or predictable, recursion can adapt
dynamically to solve the problem.
► Example: Generating permutations or subsets of a set.
Page 39 Prof. Sarju S, Department of Computer Science and Engineering, SJCET Palai
Thank You
Prof. Sarju S
Department of Computer Science and Engineering
St. Joseph’s College of Engineering and Technology, Palai (Autonomous)
sarju.s@sjcetpalai.ac.in
Page 40 Disclaimer - This document contains images/texts from various internet sources. Copyright belongs to the respective content creators.
Document is compiled exclusively for study purpose and shall not be used for commercial purpose.
