C Programming (DSA)
DSU - Day 9
Today’s Agenda
● Recursion Basics
● Binary Search Algorithm
● Recursion vs Iteration
● Recursive Cases
What is recursion?
● Recursion is a programming technique where a function calls
itself to solve a problem by breaking it down into smaller,
simpler sub-problems.
Key Components of Recursion:
● Base Case: The condition under which the recursion stops.
● Recursive Case: The part where the function calls itself.
Why Use Recursion?
● Helps solve complex problems by dividing them into simpler sub-problems.
● Ideal for tasks like tree traversal, factorials, Fibonacci series, and divide-and-
conquer algorithms.
Real-World Analogy
Imagine two mirrors facing each other—you see an infinite reflection going deeper and deeper.
That’s how recursion works: each function call reflects another until a stopping point (base case) is
reached.
Recursion in C
Syntax:
void recursiveFunction(parameters) {
if (base_condition) {
// Stop recursion
return;
} else {
// Recursive call with updated parameters
recursiveFunction(modified_parameters);
}
}
Example :Print Numbers 1 to 5 Recursively
void printNumbers(int n)
{
if (n > 5) return; // Base case
printf("%d\n", n); // Output
printNumbers(n + 1); // Recursive
call
}
Example Program:
// Simple recursive function
void sayHello(int n)
{
if (n == 0) return; // Base case
printf("Hello\n");
sayHello(n - 1); // Recursive call
}
Explanation of Output:
A step-by-step stack build-up:
Step 1: printNumbers(1)
Step 2: printNumbers(2)
Step 3: printNumbers(3)
Step 4: printNumbers(4)
Step 5: printNumbers(5)
Step 6: printNumbers(6) → Base case hit → return
Each function returns:
● Return from printNumbers(5)
● Return from printNumbers(4)
● Return from printNumbers(3)
● Return from printNumbers(2)
● Return from printNumbers(1)
Types of Recursion
1. Direct Recursion
2. Indirect Recursion
3. Tail Recursion
4. Head (No-Tail) Recursion
1. Direct Recursion—A function calls itself directly.
void directRecursion()
// Base case
if (condition) return;
directRecursion(); // Direct call
}
2. Indirect Recursion—Two or more functions call each other in a
cycle.
void functionA() {
if (conditionA) return;
functionB(); // Calls B
void functionB() {
if (conditionB) return;
functionA(); // Calls A
}
3. Tail Recursion—A recursive call is the last statement in the
function.
void tailRecursion(int n)
if (n == 0) return;
tailRecursion(n - 1); // Last operation
}
4. Head Recursion—A recursive call is made before any other
operation.
void headRecursion(int n)
if (n == 0) return;
headRecursion(n - 1); // First operation
printf("%d\n", n); // After recursion
}
C Program - Factorial Using Recursion
#include <stdio.h>
int factorial(int n) {
// Base case: factorial of 0 or 1 is 1
if (n == 0 || n == 1)
return 1;
// Recursive case: n * factorial of (n - 1)
return n * factorial(n - 1);
}
int main() {
int num;
// Ask user to enter a number
printf("Enter a positive integer: ");
scanf("%d", &num);
// Check for negative input
if (num < 0)
printf("Factorial is not defined for negative numbers.\n");
else {
// Call the recursive function and print the result
int result = factorial(num);
printf("Factorial of %d is %d\n", num, result);
}
return 0;
}
Flow of the program
[Start]
↓
[Input n]
↓
[Is n < 0?] ── Yes ──▶ [Print "Not defined"] ──▶ [End]
│
No
↓
[Call factorial(n)]
↓
┌────────────────────────────┐
│ Recursive Function Begins │
└────────────────────────────┘
↓
[Is n == 0 or n == 1?] ── Yes ──▶ [Return 1]
│
No
↓
[Return n * factorial(n - 1)]
↓
[Result returned to main()]
↓
[Print result]
↓
[End]
Recursion Flowchart—Illustrate recursion call stack.
Example: Factorial Function factorial(n)
Function Call Sequence (n = 3):
factorial(3)
└── factorial(2)
└── factorial(1)
└── factorial(0) → returns 1
← returns 1 × 1 = 1
← returns 2 × 1 = 2
← returns 3 × 2 = 6
Advantages:
● Simpler code for complex problems (e.g., tree traversal)
● Elegant logic for divide-and-conquer algorithms
● Reduces need for explicit loops or stacks
Disadvantages:
● Memory overhead due to call stack
● Risk of stack overflow if base case is missing or too deep
● Less efficient than iteration in some cases (e.g., naive
Fibonacci
Binary Search Algorithm in C
Binary Search is a fast search algorithm used to find an element in a
sorted array by repeatedly dividing the search range in half.
It follows the Divide and Conquer principle.
How Binary Search Works:
1. Start with the middle element of the array.
2. If it matches the target, return its index.
3. If the target is less than the middle, search the
left half.
4. If the target is greater, search the right half.
5. Repeat until the element is found or the range is
empty.
Binary Search vs. Linear Search
● Use Binary Search for large, sorted datasets.
● Use Linear Search for small or unsorted arrays.
Binary Search – Algorithm
Binary Search Algorithm Steps
1. Initialize low = 0, high = n - 1
2. Repeat while low ≤ high:
○ Compute mid = (low + high) / 2
○ If arr[mid] == key, return mid
○ If arr[mid] < key, set low = mid + 1
○ If arr[mid] > key, set high = mid - 1
3. If not found, return -1
Binary Search Flowchart
Trace Example – Step-by-Step
Binary Search—C Code
Example: Search for 7 in [1, 3, 5, 7, 9, 11]
Binary Search – Edge Cases
🔸 Key Not Found
● Array: {2, 4, 6, 8}
● Key: 5
● Result: -1
🔸 Key is First Element
● Array: {10, 20, 30}
● Key: 10
● Result: 0
Binary Search – Edge Cases
🔸 Key is Last Element
● Array: {10, 20, 30}
● Key: 30
● Result: 2
🔸 Duplicate Elements
● Array: {5, 5, 5, 5}
● Key: 5
● Result: Any index from 0 to 3 (depends on implementation)
Applications of Binary Search
Recursion vs. Iteration:
Iteration is the process of repeating instructions using loops like for,
while, or do-while.
It continues until a condition is false, without using function calls.
Structure Comparison: Recursion vs. Iteration
Factorial Using Recursion:
int factorialRecursive(int n) {
if (n == 0 || n == 1)
return 1;
return n * factorialRecursive(n - 1);
}
Structure Comparison: Recursion vs. Iteration
Factorial Using Iteration:
int factorialIterative(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
Memory and Speed Comparison:
Recursion vs. Iteration – Termination
Recursion vs. Iteration—Readability and Code Size
Recursion vs. Iteration— Performance Comparison Table
Fibonacci Series – Recursion vs. Iteration
Recursive Method:
int fibonacciRecursive(int n)
{
if (n <= 1)
return n;
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
🔹 Pros: Simple, elegant
🔹 Cons: Inefficient for large n due to repeated calculation
Fibonacci Series – Recursion vs. Iteration
Iteration Method:
int fibonacciIterative(int n) {
int a = 0, b = 1, next;
for (int i = 0; i < n; i++) {
printf("%d ", a);
next = a + b;
a = b;
b = next;
}
}
🔹 Pros: Simple, elegant
🔹 Cons: Inefficient for large n due to repeated calculation
Summary – Recursion vs. Iteration
✅ Recursion
● The function calls itself
● Uses call stack memory
● Elegant for divide-and-conquer problems
● Risk of stack overflow
● Harder to debug
Summary – Recursion vs. Iteration
✅ Iteration
● Uses loops (for, while)
● Constant memory usage
● Faster and more efficient
● Easier to debug and trace
● Better for simple repetitive tasks
Use case Recursion Programs
1. Factorial using recursion
#include <stdio.h>
// Recursive function to calculate factorial
int factorial(int n) {
if(n == 0 || n == 1)
return 1; // Base case
else
return n * factorial(n - 1); // Recursive call
}
int main() {
int number;
printf("Enter a positive integer: ");
scanf("%d", &number);
printf("Factorial of %d is %d\n", number, factorial(number));
return 0;
}
Use case Recursion Programs
2. Fibonacci using recursion
#include <stdio.h>
// Recursive function to calculate nth Fibonacci number
int fibonacci(int n) {
if (n == 0)
return 0; // Base case 1
else if (n == 1)
return 1; // Base case 2
else
return fibonacci(n - 1) + fibonacci(n - 2); // Recursive call
}
int main() {
int n, i;
printf("Enter the number of terms: ");
scanf("%d", &n);
printf("Fibonacci Series: ");
for(i = 0; i < n; i++) {
printf("%d ", fibonacci(i));
}
printf("\n");
return 0;
}
Use case Recursion Programs
3. Sum of digits (recursive)
#include <stdio.h>
// Recursive function to calculate sum of digits
int sumOfDigits(int n) {
if (n == 0)
return 0; // Base case
else
return (n % 10) + sumOfDigits(n / 10); // Recursive call
}
int main() {
int number;
printf("Enter a number: ");
scanf("%d", &number);
printf("Sum of digits of %d is %d\n", number, sumOfDigits(number));
return 0;
}
Use case Binary Search Problems
1. Basic Binary Search
#include <stdio.h>
int binarySearch(int arr[], int n, int key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // To avoid overflow
if (arr[mid] == key)
return mid; // Key found, return index
else if (arr[mid] < key)
left = mid + 1; // Search right half
else
right = mid - 1; // Search left half
} return -1; // Key not found }
int main() {
int arr[] = {2, 4, 7, 10, 23, 55, 73};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 23;
int result = binarySearch(arr, n, key);
if (result != -1)
printf("Element found at index %d\n", result);
else
printf("Element not found\n");
return 0;
}
Use case Binary Search Problems
2. First occurrence of element
#include <stdio.h>
int firstOccurrence(int arr[], int n, int key) {
int left = 0, right = n - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) {
result = mid; // store result
right = mid - 1; // go left to check for earlier occurrence
} else if (arr[mid] < key) {
left = mid + 1; // search right half
}
else {
right = mid - 1; // search left half
}
}
return result;
}
int main() {
int arr[] = {2, 4, 4, 4, 10, 23, 55};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 4;
int index = firstOccurrence(arr, n, key);
if (index != -1)
printf("First occurrence of %d is at index %d\n", key, index);
else
printf("Element not found\n");
return 0;
}
Use case Binary Search Problems
3. Last occurrence of element
#include <stdio.h>
int lastOccurrence(int arr[], int n, int key) {
int left = 0, right = n - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) {
result = mid; // store result
left = mid + 1; // go right to check for later occurrence
} else if (arr[mid] < key) {
left = mid + 1; // search right half
}
else {
right = mid - 1; // search left half
}
}
return result;
}
int main() {
int arr[] = {2, 4, 4, 4, 10, 23, 55};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 4;
int index = lastOccurrence(arr, n, key);
if (index != -1)
printf("Last occurrence of %d is at index %d\n", key, index);
else
printf("Element not found\n");
return 0;
}
Thank You
