c
examples
examples.c🔧c
/**
* @file examples.c
* @brief Recursion Examples
*
* This file demonstrates recursive functions in C.
*
* Compile: gcc -Wall examples.c -o examples
* Run: ./examples
*/
#include <stdio.h>
#include <string.h>
/* ============================================================
* EXAMPLE 1: FACTORIAL
* ============================================================ */
int factorial(int n) {
// Base case
if (n <= 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
void example_factorial() {
printf("\n=== Example 1: Factorial ===\n");
for (int i = 0; i <= 10; i++) {
printf("%2d! = %d\n", i, factorial(i));
}
}
/* ============================================================
* EXAMPLE 2: FIBONACCI
* ============================================================ */
int fibonacci(int n) {
// Base cases
if (n <= 0) return 0;
if (n == 1) return 1;
// Recursive case
return fibonacci(n - 1) + fibonacci(n - 2);
}
void example_fibonacci() {
printf("\n=== Example 2: Fibonacci ===\n");
printf("Fibonacci sequence: ");
for (int i = 0; i <= 15; i++) {
printf("%d ", fibonacci(i));
}
printf("\n");
}
/* ============================================================
* EXAMPLE 3: SUM OF ARRAY
* ============================================================ */
int sumArray(int arr[], int size) {
// Base case
if (size <= 0) return 0;
// Recursive case: last element + sum of rest
return arr[size - 1] + sumArray(arr, size - 1);
}
void example_sum_array() {
printf("\n=== Example 3: Sum of Array ===\n");
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Array: [1, 2, 3, 4, 5]\n");
printf("Sum: %d\n", sumArray(arr, size));
}
/* ============================================================
* EXAMPLE 4: POWER FUNCTION
* ============================================================ */
int power(int base, int exp) {
// Base case
if (exp == 0) return 1;
// Recursive case
return base * power(base, exp - 1);
}
// Optimized version: O(log n)
int powerOptimized(int base, int exp) {
if (exp == 0) return 1;
if (exp == 1) return base;
int half = powerOptimized(base, exp / 2);
if (exp % 2 == 0) {
return half * half;
} else {
return base * half * half;
}
}
void example_power() {
printf("\n=== Example 4: Power Function ===\n");
printf("2^10 = %d (recursive)\n", power(2, 10));
printf("2^10 = %d (optimized)\n", powerOptimized(2, 10));
printf("3^5 = %d\n", power(3, 5));
}
/* ============================================================
* EXAMPLE 5: COUNTDOWN
* ============================================================ */
void countdown(int n) {
// Base case
if (n < 0) {
printf("Blast off!\n");
return;
}
// Process before recursive call
printf("%d... ", n);
// Recursive call
countdown(n - 1);
}
void example_countdown() {
printf("\n=== Example 5: Countdown ===\n");
countdown(5);
}
/* ============================================================
* EXAMPLE 6: PRINT DIGITS
* ============================================================ */
void printDigits(int n) {
// Base case
if (n == 0) return;
// Recursive call first (head recursion)
printDigits(n / 10);
// Then print
printf("%d ", n % 10);
}
void printDigitsReverse(int n) {
// Base case
if (n == 0) return;
// Print first (processes before recursion)
printf("%d ", n % 10);
// Then recursive call
printDigitsReverse(n / 10);
}
void example_print_digits() {
printf("\n=== Example 6: Print Digits ===\n");
int num = 12345;
printf("Digits of %d (forward): ", num);
printDigits(num);
printf("\n");
printf("Digits of %d (reverse): ", num);
printDigitsReverse(num);
printf("\n");
}
/* ============================================================
* EXAMPLE 7: STRING REVERSE
* ============================================================ */
void printStringReverse(char str[], int index) {
// Base case
if (str[index] == '\0') return;
// Recursive call first
printStringReverse(str, index + 1);
// Print after returning
printf("%c", str[index]);
}
void example_string_reverse() {
printf("\n=== Example 7: String Reverse ===\n");
char str[] = "Hello World";
printf("Original: %s\n", str);
printf("Reversed: ");
printStringReverse(str, 0);
printf("\n");
}
/* ============================================================
* EXAMPLE 8: GCD (EUCLIDEAN ALGORITHM)
* ============================================================ */
int gcd(int a, int b) {
// Base case
if (b == 0) return a;
// Recursive case
return gcd(b, a % b);
}
void example_gcd() {
printf("\n=== Example 8: GCD ===\n");
printf("GCD(48, 18) = %d\n", gcd(48, 18));
printf("GCD(100, 35) = %d\n", gcd(100, 35));
printf("GCD(17, 13) = %d\n", gcd(17, 13));
}
/* ============================================================
* EXAMPLE 9: SUM OF DIGITS
* ============================================================ */
int sumOfDigits(int n) {
// Handle negative
if (n < 0) n = -n;
// Base case
if (n == 0) return 0;
// Recursive case
return (n % 10) + sumOfDigits(n / 10);
}
void example_sum_digits() {
printf("\n=== Example 9: Sum of Digits ===\n");
printf("Sum of digits of 12345: %d\n", sumOfDigits(12345));
printf("Sum of digits of 999: %d\n", sumOfDigits(999));
printf("Sum of digits of 1000: %d\n", sumOfDigits(1000));
}
/* ============================================================
* EXAMPLE 10: BINARY REPRESENTATION
* ============================================================ */
void printBinary(int n) {
// Base case
if (n == 0) return;
// Recursive call first (to print MSB first)
printBinary(n / 2);
// Print current bit
printf("%d", n % 2);
}
void example_binary() {
printf("\n=== Example 10: Binary Representation ===\n");
int numbers[] = {10, 255, 1, 7, 16};
int size = sizeof(numbers) / sizeof(numbers[0]);
for (int i = 0; i < size; i++) {
printf("%3d in binary: ", numbers[i]);
if (numbers[i] == 0) printf("0");
else printBinary(numbers[i]);
printf("\n");
}
}
/* ============================================================
* EXAMPLE 11: BINARY SEARCH (RECURSIVE)
* ============================================================ */
int binarySearch(int arr[], int left, int right, int target) {
// Base case: not found
if (left > right) return -1;
int mid = left + (right - left) / 2;
// Found
if (arr[mid] == target) return mid;
// Search left or right half
if (arr[mid] > target) {
return binarySearch(arr, left, mid - 1, target);
} else {
return binarySearch(arr, mid + 1, right, target);
}
}
void example_binary_search() {
printf("\n=== Example 11: Binary Search ===\n");
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]\n");
int targets[] = {23, 100, 2, 91};
for (int i = 0; i < 4; i++) {
int result = binarySearch(arr, 0, size - 1, targets[i]);
printf("Search %d: %s", targets[i],
result >= 0 ? "Found at index " : "Not found");
if (result >= 0) printf("%d", result);
printf("\n");
}
}
/* ============================================================
* EXAMPLE 12: PALINDROME CHECK
* ============================================================ */
int isPalindromeHelper(char str[], int start, int end) {
// Base case: single char or empty
if (start >= end) return 1;
// If characters don't match
if (str[start] != str[end]) return 0;
// Check remaining string
return isPalindromeHelper(str, start + 1, end - 1);
}
int isPalindrome(char str[]) {
return isPalindromeHelper(str, 0, strlen(str) - 1);
}
void example_palindrome() {
printf("\n=== Example 12: Palindrome Check ===\n");
char *words[] = {"radar", "hello", "level", "world", "racecar"};
int n = 5;
for (int i = 0; i < n; i++) {
printf("'%s': %s\n", words[i],
isPalindrome(words[i]) ? "Palindrome" : "Not palindrome");
}
}
/* ============================================================
* EXAMPLE 13: TOWER OF HANOI
* ============================================================ */
void towerOfHanoi(int n, char from, char to, char aux) {
// Base case
if (n == 1) {
printf("Move disk 1 from %c to %c\n", from, to);
return;
}
// Move n-1 disks from 'from' to 'aux'
towerOfHanoi(n - 1, from, aux, to);
// Move nth disk from 'from' to 'to'
printf("Move disk %d from %c to %c\n", n, from, to);
// Move n-1 disks from 'aux' to 'to'
towerOfHanoi(n - 1, aux, to, from);
}
void example_hanoi() {
printf("\n=== Example 13: Tower of Hanoi ===\n");
printf("Solution for 3 disks:\n");
towerOfHanoi(3, 'A', 'C', 'B');
}
/* ============================================================
* EXAMPLE 14: TAIL RECURSION
* ============================================================ */
// Not tail recursive - multiplication after call
int factorialNonTail(int n) {
if (n <= 1) return 1;
return n * factorialNonTail(n - 1); // Operation after call
}
// Tail recursive - result passed as parameter
int factorialTailHelper(int n, int accumulator) {
if (n <= 1) return accumulator;
return factorialTailHelper(n - 1, n * accumulator); // Last operation
}
int factorialTail(int n) {
return factorialTailHelper(n, 1);
}
void example_tail_recursion() {
printf("\n=== Example 14: Tail Recursion ===\n");
printf("Non-tail recursive 5! = %d\n", factorialNonTail(5));
printf("Tail recursive 5! = %d\n", factorialTail(5));
}
/* ============================================================
* EXAMPLE 15: MEMOIZED FIBONACCI
* ============================================================ */
long long fibMemo[100] = {0};
long long fibonacciMemoized(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
// Check if already computed
if (fibMemo[n] != 0) return fibMemo[n];
// Compute and store
fibMemo[n] = fibonacciMemoized(n - 1) + fibonacciMemoized(n - 2);
return fibMemo[n];
}
void example_memoization() {
printf("\n=== Example 15: Memoized Fibonacci ===\n");
printf("Fibonacci with memoization:\n");
for (int i = 0; i <= 40; i += 10) {
printf("F(%d) = %lld\n", i, fibonacciMemoized(i));
}
}
/* ============================================================
* MAIN FUNCTION
* ============================================================ */
int main() {
printf("╔════════════════════════════════════════════════╗\n");
printf("║ RECURSION - EXAMPLES ║\n");
printf("║ Functions that call themselves ║\n");
printf("╚════════════════════════════════════════════════╝\n");
example_factorial();
example_fibonacci();
example_sum_array();
example_power();
example_countdown();
example_print_digits();
example_string_reverse();
example_gcd();
example_sum_digits();
example_binary();
example_binary_search();
example_palindrome();
example_hanoi();
example_tail_recursion();
example_memoization();
printf("\n=== All Examples Completed! ===\n");
return 0;
}