Recursion Fundamentals - Multi-Language Examples

1. Factorial Calculation

C Implementation

#include <stdio.h>

// Recursive factorial
int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
}
return n * factorial(n - 1);
}

// Iterative factorial for comparison

int factorial_iterative(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}

// Tail recursive factorial

int factorial_tail(int n, int accumulator) {
if (n == 0) return accumulator;
return factorial_tail(n - 1, n * accumulator);
}

int main() {
int n = 5;
printf("Recursive factorial(%d) = %d\n", n, factorial(n));
printf("Iterative factorial(%d) = %d\n", n, factorial_iterative(n));
printf("Tail recursive factorial(%d) = %d\n", n, factorial_tail(n, 1));
return 0;
}
Java Implementation

public class Factorial {

// Recursive factorial
public static int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
}
return n * factorial(n - 1);
}

// Iterative factorial
public static int factorialIterative(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
 result *= i;
}
return result;
}

// Tail recursive factorial with helper

public static int factorialTail(int n) {
return factorialTailHelper(n, 1);
}

private static int factorialTailHelper(int n, int accumulator) {

if (n == 0) return accumulator;
return factorialTailHelper(n - 1, n * accumulator);
}

public static void main(String[] args) {

int n = 5;
[Link]("Recursive factorial(" + n + ") = " + factorial(n));
[Link]("Iterative factorial(" + n + ") = " + factorialIterative(n));
[Link]("Tail recursive factorial(" + n + ") = " + factorialTail(n));
}
}

Python Implementation
def factorial(n):
"""Recursive factorial"""
if n == 0 or n == 1:
return 1
return n * factorial(n - 1)

def factorial_iterative(n):
"""Iterative factorial"""
result = 1
for i in range(1, n + 1):
result *= i
return result

def factorial_tail(n, accumulator=1):

"""Tail recursive factorial"""
if n == 0:
return accumulator
return factorial_tail(n - 1, n * accumulator)

if __name__ == "__main__":
n=5
print(f"Recursive factorial({n}) = {factorial(n)}")
print(f"Iterative factorial({n}) = {factorial_iterative(n)}")
print(f"Tail recursive factorial({n}) = {factorial_tail(n)}")
 2. Fibonacci Sequence
C Implementation
#include <stdio.h>
#include <stdlib.h>

// Basic recursive Fibonacci (inefficient)

int fibonacci(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}

// Memoized Fibonacci
#define MAX 100
int memo[MAX];

void init_memo() {
for (int i = 0; i < MAX; i++) {
memo[i] = -1;
}
}

int fibonacci_memo(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;

if (memo[n] != -1) {
return memo[n];
}

memo[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2);

return memo[n];
}

// Iterative Fibonacci
int fibonacci_iterative(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;

int prev = 0, curr = 1, next;

for (int i = 2; i <= n; i++) {
next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}

int main() {
int n = 10;
printf("Basic recursive Fibonacci(%d) = %d\n", n, fibonacci(n));
 init_memo();
printf("Memoized Fibonacci(%d) = %d\n", n, fibonacci_memo(n));
printf("Iterative Fibonacci(%d) = %d\n", n, fibonacci_iterative(n));
return 0;
}

Java Implementation
import [Link];
import [Link];

public class Fibonacci {

// Basic recursive Fibonacci
public static int fibonacci(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}

// Memoized Fibonacci
private static Map<Integer, Integer> memo = new HashMap<>();

public static int fibonacciMemo(int n) {

if (n <= 0) return 0;
if (n == 1) return 1;

if ([Link](n)) {
return [Link](n);
}

int result = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);

[Link](n, result);
return result;
}

// Iterative Fibonacci
public static int fibonacciIterative(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;

int prev = 0, curr = 1, next;

for (int i = 2; i <= n; i++) {
next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}

public static void main(String[] args) {

int n = 10;
 [Link]("Basic recursive Fibonacci(" + n + ") = " + fibonacci(n));
[Link]("Memoized Fibonacci(" + n + ") = " + fibonacciMemo(n));
[Link]("Iterative Fibonacci(" + n + ") = " + fibonacciIterative(n));

// Print Fibonacci sequence

[Link]("Fibonacci sequence up to " + n + ": ");
for (int i = 0; i <= n; i++) {
[Link](fibonacciMemo(i) + " ");
}
[Link]();
}
}
Python Implementation
def fibonacci(n):
"""Basic recursive Fibonacci"""
if n <= 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)

# Memoized Fibonacci
def fibonacci_memo(n, memo=None):
if memo is None:
memo = {}

if n <= 0:
return 0
if n == 1:
return 1

if n in memo:
return memo[n]

memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)

return memo[n]

def fibonacci_iterative(n):
"""Iterative Fibonacci"""
if n <= 0:
return 0
if n == 1:
return 1

prev, curr = 0, 1
for _ in range(2, n + 1):
next_num = prev + curr
prev, curr = curr, next_num

return curr
if __name__ == "__main__":
n = 10

print(f"Basic recursive Fibonacci({n}) = {fibonacci(n)}")

print(f"Memoized Fibonacci({n}) = {fibonacci_memo(n)}")
print(f"Iterative Fibonacci({n}) = {fibonacci_iterative(n)}")

# Print Fibonacci sequence

print(f"Fibonacci sequence up to {n}:", end=" ")
for i in range(n + 1):
print(fibonacci_memo(i), end=" ")
print()

3. Sum of Digits
C Implementation

#include <stdio.h>

// Recursive sum of digits

int sum_of_digits(int n) {
if (n == 0) {
return 0;
}
return (n % 10) + sum_of_digits(n / 10);
}

// Tail recursive version

int sum_of_digits_tail(int n, int accumulator) {
if (n == 0) {
return accumulator;
}
return sum_of_digits_tail(n / 10, accumulator + (n % 10));
}

int main() {
int num = 12345;

printf("Sum of digits of %d (recursive) = %d\n",

num, sum_of_digits(num));
printf("Sum of digits of %d (tail recursive) = %d\n",
num, sum_of_digits_tail(num, 0));

return 0;
}

Java Implementation

public class SumOfDigits {

// Recursive sum of digits
public static int sumOfDigits(int n) {
if (n == 0) {
 return 0;
}
return (n % 10) + sumOfDigits(n / 10);
}

// Tail recursive version

public static int sumOfDigitsTail(int n) {
return sumOfDigitsTailHelper(n, 0);
}

private static int sumOfDigitsTailHelper(int n, int accumulator) {

if (n == 0) {
return accumulator;
}
return sumOfDigitsTailHelper(n / 10, accumulator + (n % 10));
}

public static void main(String[] args) {

int num = 12345;

[Link]("Sum of digits of " + num +

" (recursive) = " + sumOfDigits(num));
[Link]("Sum of digits of " + num +
" (tail recursive) = " + sumOfDigitsTail(num));
}
}

Python Implementation

def sum_of_digits(n):
"""Recursive sum of digits"""
if n == 0:
return 0
return (n % 10) + sum_of_digits(n // 10)

def sum_of_digits_tail(n, accumulator=0):

"""Tail recursive sum of digits"""
if n == 0:
return accumulator
return sum_of_digits_tail(n // 10, accumulator + (n % 10))

if __name__ == "__main__":
num = 12345

print(f"Sum of digits of {num} (recursive) = {sum_of_digits(num)}")

print(f"Sum of digits of {num} (tail recursive) = {sum_of_digits_tail(num)}")
 4. String Reversal
C Implementation

#include <stdio.h>
#include <string.h>

// Helper function for recursion

void reverse_string_helper(char* str, int start, int end) {
if (start >= end) {
return;
}

// Swap characters
char temp = str[start];
str[start] = str[end];
str[end] = temp;

// Recursive call
reverse_string_helper(str, start + 1, end - 1);
}

// Recursive string reversal

void reverse_string(char* str) {
int length = strlen(str);
if (length > 1) {
reverse_string_helper(str, 0, length - 1);
}
}

int main() {
char str[] = "hello";
char original[20];
strcpy(original, str); // Keep original

printf("Original string: %s\n", original);

reverse_string(str);
printf("Reversed string: %s\n", str);

return 0;
}

Java Implementation

public class StringReversal {

// Recursive string reversal
public static String reverseString(String str) {
if (str == null || [Link]() <= 1) {
return str;
}
return reverseString([Link](1)) + [Link](0);
 }

// Recursive with char array (more efficient)

public static String reverseStringEfficient(String str) {
char[] chars = [Link]();
reverseHelper(chars, 0, [Link] - 1);
return new String(chars);
}

private static void reverseHelper(char[] chars, int start, int end) {

if (start >= end) {
return;
}

// Swap characters
char temp = chars[start];
chars[start] = chars[end];
chars[end] = temp;

// Recursive call
reverseHelper(chars, start + 1, end - 1);
}

public static void main(String[] args) {

String str = "hello";

[Link]("Original string: " + str);

[Link]("Reversed (simple): " + reverseString(str));
[Link]("Reversed (efficient): " + reverseStringEfficient(str));
}
}

Python Implementation

def reverse_string(s):
"""Recursive string reversal"""
if len(s) <= 1:
return s
return reverse_string(s[1:]) + s[0]

def reverse_string_list(s):
"""Recursive reversal using list conversion"""
def reverse_helper(chars, start, end):
if start >= end:
return
chars[start], chars[end] = chars[end], chars[start]
reverse_helper(chars, start + 1, end - 1)

chars = list(s)
reverse_helper(chars, 0, len(chars) - 1)
return ''.join(chars)
if __name__ == "__main__":
s = "hello"

print(f"Original string: {s}")

print(f"Reversed (simple): {reverse_string(s)}")
print(f"Reversed (list method): {reverse_string_list(s)}")

5. Binary Search (Recursive)

C Implementation

#include <stdio.h>

// Recursive binary search

int binary_search(int arr[], int left, int right, int target) {
if (left > right) {
return -1; // Element not found
}

int mid = left + (right - left) / 2;

if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
return binary_search(arr, left, mid - 1, target);
} else {
return binary_search(arr, mid + 1, right, target);
}
}

int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 23;

int result = binary_search(arr, 0, n - 1, target);

if (result != -1) {
printf("Element %d found at index %d\n", target, result);
} else {
printf("Element %d not found in array\n", target);
}

return 0;
}

Java Implementation

public class BinarySearch {

// Recursive binary search
public static int binarySearch(int[] arr, int left, int right, int target) {
 if (left > right) {
return -1; // Element not found
}

int mid = left + (right - left) / 2;

if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
return binarySearch(arr, left, mid - 1, target);
} else {
return binarySearch(arr, mid + 1, right, target);
}
}

public static void main(String[] args) {

int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23;

int result = binarySearch(arr, 0, [Link] - 1, target);

if (result != -1) {
[Link]("Element " + target + " found at index " + result);
} else {
[Link]("Element " + target + " not found in array");
}

// Test with element not in array

target = 100;
result = binarySearch(arr, 0, [Link] - 1, target);
[Link]("Search for " + target + " returned: " + result);
}
}

Python Implementation

def binary_search(arr, left, right, target):

"""Recursive binary search"""
if left > right:
return -1 # Element not found

mid = left + (right - left) // 2

if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, left, mid - 1, target)
else:
return binary_search(arr, mid + 1, right, target)

if __name__ == "__main__":
 arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23

result = binary_search(arr, 0, len(arr) - 1, target)

if result != -1:
print(f"Element {target} found at index {result}")
else:
print(f"Element {target} not found in array")

# Test with element not in array

target = 100
result = binary_search(arr, 0, len(arr) - 1, target)
print(f"Search for {target} returned: {result}")

6. Tree Traversal (Directory Structure)

C Implementation

#include <stdio.h>
#include <dirent.h>
#include <sys/stat.h>
#include <string.h>

// Recursive directory traversal

void list_files_recursive(const char* path, int depth) {
DIR* dir;
struct dirent* entry;
struct stat statbuf;
char full_path[1024];

if (!(dir = opendir(path))) {
return;
}

while ((entry = readdir(dir)) != NULL) {

// Skip . and .. directories
if (strcmp(entry->d_name, ".") == 0 ||
strcmp(entry->d_name, "..") == 0) {
continue;
}

// Build full path

snprintf(full_path, sizeof(full_path), "%s/%s", path, entry->d_name);

// Get file stats

if (stat(full_path, &statbuf) == -1) {
continue;
}

// Print indentation
for (int i = 0; i < depth; i++) {
 printf(" ");
}

if (S_ISDIR(statbuf.st_mode)) {
printf("[%s]\n", entry->d_name);
// Recursive call for subdirectory
list_files_recursive(full_path, depth + 1);
} else {
printf("%s\n", entry->d_name);
}
}

closedir(dir);
}

int main() {
const char* path = ".";
printf("Directory structure of '%s':\n", path);
list_files_recursive(path, 0);
return 0;
}

Java Implementation

import [Link];
import [Link];

public class DirectoryTraversal {

// Recursive directory traversal
public static void listFilesRecursive(File dir, int depth) {
if (![Link]() || ![Link]()) {
return;
}

File[] files = [Link]();

if (files == null) {
return;
}

for (File file : files) {

// Skip hidden files
if ([Link]()) {
continue;
}

// Print indentation
for (int i = 0; i < depth; i++) {
[Link](" ");
}

if ([Link]()) {
 [Link]("[" + [Link]() + "]");
// Recursive call for subdirectory
listFilesRecursive(file, depth + 1);
} else {
[Link]([Link]());
}
}
}

public static void main(String[] args) {

String path = ".";
[Link]("Directory structure of '" + path + "':");
listFilesRecursive(new File(path), 0);
}
}

Python Implementation

import os

def list_files_recursive(path, depth=0):

"""Recursive directory traversal"""
try:
items = [Link](path)
except PermissionError:
return

for item in items:

# Skip hidden files/folders
if [Link]('.'):
continue

full_path = [Link](path, item)

# Print indentation
print(" " * depth, end="")

if [Link](full_path):
print(f"[{item}]")
# Recursive call for subdirectory
list_files_recursive(full_path, depth + 1)
else:
print(item)

if __name__ == "__main__":
path = "."
print(f"Directory structure of '{path}':")
list_files_recursive(path)
7. Tower of Hanoi
C Implementation
#include <stdio.h>

// Recursive Tower of Hanoi

void tower_of_hanoi(int n, char source, char destination, char auxiliary) {
if (n == 1) {
printf("Move disk 1 from %c to %c\n", source, destination);
return;
}

tower_of_hanoi(n - 1, source, auxiliary, destination);

printf("Move disk %d from %c to %c\n", n, source, destination);
tower_of_hanoi(n - 1, auxiliary, destination, source);
}

int main() {
int n = 3;
printf("Tower of Hanoi solution for %d disks:\n", n);
tower_of_hanoi(n, 'A', 'C', 'B');
return 0;
}

Java Implementation

public class TowerOfHanoi {

// Recursive Tower of Hanoi
public static void towerOfHanoi(int n, char source, char destination, char auxiliary) {
if (n == 1) {
[Link]("Move disk 1 from " + source + " to " + destination);
return;
}

towerOfHanoi(n - 1, source, auxiliary, destination);

[Link]("Move disk " + n + " from " + source + " to " + destination);
towerOfHanoi(n - 1, auxiliary, destination, source);
}

public static void main(String[] args) {

int n = 3;
[Link]("Tower of Hanoi solution for " + n + " disks:");
towerOfHanoi(n, 'A', 'C', 'B');
}
}

Python Implementation

def tower_of_hanoi(n, source, destination, auxiliary):

"""Recursive Tower of Hanoi"""
if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return
 tower_of_hanoi(n - 1, source, auxiliary, destination)
print(f"Move disk {n} from {source} to {destination}")
tower_of_hanoi(n - 1, auxiliary, destination, source)

if __name__ == "__main__":
n=3
print(f"Tower of Hanoi solution for {n} disks:")
tower_of_hanoi(n, 'A', 'C', 'B')

8. Palindrome Check
C Implementation

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>

// Helper function to clean string (remove spaces, punctuation, lowercase)

void clean_string(char* str, char* cleaned) {
int j = 0;
for (int i = 0; str[i] != '\0'; i++) {
if (isalnum(str[i])) {
cleaned[j++] = tolower(str[i]);
}
}
cleaned[j] = '\0';
}

// Recursive palindrome check

bool is_palindrome_recursive(char* str, int left, int right) {
// Base case: single character or empty substring
if (left >= right) {
return true;
}

// If characters don't match

if (str[left] != str[right]) {
return false;
}

// Recursive case: check inner substring

return is_palindrome_recursive(str, left + 1, right - 1);
}

// Main palindrome function

bool is_palindrome(char* str) {
char cleaned[100];
clean_string(str, cleaned);
int len = strlen(cleaned);

if (len == 0) {
 return true; // Empty string is palindrome
}

return is_palindrome_recursive(cleaned, 0, len - 1);

}

// Alternative: Simple string reversal comparison

bool is_palindrome_simple(char* str) {
char cleaned[100];
clean_string(str, cleaned);
int len = strlen(cleaned);

for (int i = 0; i < len / 2; i++) {

if (cleaned[i] != cleaned[len - 1 - i]) {
return false;
}
}
return true;
}

// Test function
void test_palindrome() {
char* test_cases[] = {
"racecar",
"A man, a plan, a canal: Panama",
"hello",
"Was it a car or a cat I saw?",
"madam",
"",
"a",
"abba",
"abcba"
};

int num_tests = sizeof(test_cases) / sizeof(test_cases[0]);

printf("Palindrome Tests:\n");
printf("================\n");

for (int i = 0; i < num_tests; i++) {

bool result = is_palindrome(test_cases[i]);
printf("'%s' -> %s\n",
test_cases[i],
result ? "Palindrome ✓" : "Not palindrome ✗");
}
}

int main() {
test_palindrome();
return 0;
}
Java Implementation

import [Link];

public class PalindromeChecker {

// Clean string: remove non-alphanumeric, convert to lowercase

private static String cleanString(String str) {
StringBuilder cleaned = new StringBuilder();
for (int i = 0; i < [Link](); i++) {
char c = [Link](i);
if ([Link](c)) {
[Link]([Link](c));
}
}
return [Link]();
}

// Recursive palindrome check

private static boolean isPalindromeRecursive(String str, int left, int right) {
// Base cases
if (left >= right) {
return true;
}

// Check if characters match

if ([Link](left) != [Link](right)) {
return false;
}

// Recursive call for inner substring

return isPalindromeRecursive(str, left + 1, right - 1);
}

// Main palindrome function

public static boolean isPalindrome(String str) {
String cleaned = cleanString(str);

// Handle empty string

if ([Link]()) {
return true;
}

return isPalindromeRecursive(cleaned, 0, [Link]() - 1);

}

// Alternative: Iterative approach

public static boolean isPalindromeIterative(String str) {
String cleaned = cleanString(str);
int left = 0;
 int right = [Link]() - 1;

while (left < right) {

if ([Link](left) != [Link](right)) {
return false;
}
left++;
right--;
}
return true;
}

// Test the implementation

public static void runTests() {
String[] testCases = {
"racecar",
"A man, a plan, a canal: Panama",
"hello",
"Was it a car or a cat I saw?",
"madam",
"",
"a",
"abba",
"abcba"
};

[Link]("Palindrome Tests:");
[Link]("================");

for (String testCase : testCases) {

boolean result = isPalindrome(testCase);
[Link]("'%s' -> %s%n",
testCase,
result ? "Palindrome ✓" : "Not palindrome ✗");
}
}

// Interactive version
public static void interactive() {
Scanner scanner = new Scanner([Link]);

while (true) {
[Link]("\nEnter a string (or 'quit' to exit): ");
String input = [Link]();

if ([Link]("quit")) {
break;
}

boolean result = isPalindrome(input);

[Link]("'%s' is %s palindrome%n",
 input,
result ? "a" : "NOT a");
}

[Link]();
[Link]("Goodbye!");
}

public static void main(String[] args) {

runTests();

// Uncomment for interactive mode

// interactive();
}
}

Python Implementation

import re
from typing import Union

def clean_string(s: str) -> str:

"""Remove non-alphanumeric characters and convert to lowercase."""
return [Link](r'[^a-zA-Z0-9]', '', s).lower()

def is_palindrome_recursive(s: str, left: int, right: int) -> bool:

"""Recursive palindrome check."""
# Base cases
if left >= right:
return True

# If characters don't match

if s[left] != s[right]:
return False

# Recursive check of inner substring

return is_palindrome_recursive(s, left + 1, right - 1)

def is_palindrome(s: str) -> bool:

"""Main palindrome checking function."""
cleaned = clean_string(s)

# Handle empty string

if not cleaned:
return True

return is_palindrome_recursive(cleaned, 0, len(cleaned) - 1)

def is_palindrome_simple(s: str) -> bool:

"""Simple iterative palindrome check."""
cleaned = clean_string(s)
 return cleaned == cleaned[::-1]

def is_palindrome_one_liner(s: str) -> bool:

"""One-liner palindrome check."""
cleaned = [Link](r'[^a-z0-9]', '', [Link]())
return cleaned == cleaned[::-1]

def test_palindrome():
"""Test the palindrome functions."""
test_cases = [
"racecar",
"A man, a plan, a canal: Panama",
"hello",
"Was it a car or a cat I saw?",
"madam",
"",
"a",
"abba",
"abcba",
"12321",
"not a palindrome"
]

print("Palindrome Tests:")
print("================\n")

for test in test_cases:

result = is_palindrome(test)
print(f"'{test}' -> {'Palindrome ✓' if result else 'Not palindrome ✗'}")

# Compare methods
print("\n\nComparison of different methods:")
print("=================================")
test_str = "A man, a plan, a canal: Panama"

print(f"Test string: '{test_str}'")

print(f"Recursive method: {is_palindrome(test_str)}")
print(f"Simple method: {is_palindrome_simple(test_str)}")
print(f"One-liner method: {is_palindrome_one_liner(test_str)}")

def interactive():
"""Interactive palindrome checker."""
print("Palindrome Checker")
print("==================")

while True:
user_input = input("\nEnter a string (or 'quit' to exit): ").strip()

if user_input.lower() == 'quit':
print("Goodbye!")
break
 if is_palindrome(user_input):
print(f"'{user_input}' is a palindrome! ✓")
else:
print(f"'{user_input}' is NOT a palindrome. ✗")

if __name__ == "__main__":
# Run tests
test_palindrome()

# Uncomment for interactive mode

# interactive()
9. Power Function (x^n)
C Implementation

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

// Recursive power function (x^n)

double power(double x, int n) {
// Base case: any number to power 0 is 1
if (n == 0) {
return 1.0;
}

// Handle negative exponents

if (n < 0) {
return 1.0 / power(x, -n);
}

// Recursive case: x^n = x * x^(n-1)

return x * power(x, n - 1);
}

// Optimized recursive power function (O(log n))

double power_optimized(double x, int n) {
// Base cases
if (n == 0) {
return 1.0;
}

if (n < 0) {
return 1.0 / power_optimized(x, -n);
}

// If n is even
if (n % 2 == 0) {
double half = power_optimized(x, n / 2);
return half * half;
}
 // If n is odd
else {
return x * power_optimized(x, n - 1);
}
}

// Iterative power function for comparison

double power_iterative(double x, int n) {
double result = 1.0;
bool negative = false;

if (n < 0) {
negative = true;
n = -n;
}

for (int i = 0; i < n; i++) {

result *= x;
}

return negative ? 1.0 / result : result;

}

// Test the power functions

void test_power() {
double base = 2.0;
int exponents[] = {0, 1, 2, 3, 4, 5, -1, -2, -3};
int num_tests = sizeof(exponents) / sizeof(exponents[0]);

printf("Power Function Tests (base = %.2f):\n", base);

printf("==================================\n");

for (int i = 0; i < num_tests; i++) {

int exp = exponents[i];

double result_simple = power(base, exp);

double result_optimized = power_optimized(base, exp);
double result_iterative = power_iterative(base, exp);
double result_math = pow(base, exp);

printf("%.2f^%d = \n", base, exp);

printf(" Simple recursive: %.6f\n", result_simple);
printf(" Optimized recursive: %.6f\n", result_optimized);
printf(" Iterative: %.6f\n", result_iterative);
printf(" Math.h pow(): %.6f\n", result_math);

// Check if all methods agree

if (fabs(result_simple - result_math) < 0.000001 &&
fabs(result_optimized - result_math) < 0.000001) {
printf(" ✓ All methods match\n");
} else {
 printf(" ✗ Discrepancy detected!\n");
}
printf("\n");
}

// Test with different bases

printf("\n\nAdditional Tests:\n");
printf("================\n");

double test_cases[][2] = {
{3.0, 4}, // 3^4 = 81
{5.0, 0}, // 5^0 = 1
{1.5, 3}, // 1.5^3 = 3.375
{0.5, 2}, // 0.5^2 = 0.25
{10.0, -2}, // 10^-2 = 0.01
{0.0, 5}, // 0^5 = 0
{2.0, 10} // 2^10 = 1024
};

for (int i = 0; i < sizeof(test_cases) / sizeof(test_cases[0]); i++) {

double b = test_cases[i][0];
int e = (int)test_cases[i][1];

double result = power_optimized(b, e);

printf("%.2f^%d = %.6f\n", b, e, result);
}
}

int main() {
test_power();
return 0;
}

Java Implementation

public class PowerFunction {

// Simple recursive power (O(n))

public static double power(double x, int n) {
// Base case
if (n == 0) {
return 1.0;
}

// Handle negative exponent

if (n < 0) {
return 1.0 / power(x, -n);
}

// Recursive case
return x * power(x, n - 1);
}

// Optimized recursive power (O(log n))

public static double powerOptimized(double x, int n) {
// Base cases
if (n == 0) {
return 1.0;
}

// Handle negative exponent

if (n < 0) {
return 1.0 / powerOptimized(x, -n);
}

// If exponent is even
if (n % 2 == 0) {
double half = powerOptimized(x, n / 2);
return half * half;
}
// If exponent is odd
else {
return x * powerOptimized(x, n - 1);
}
}

// Iterative power function

public static double powerIterative(double x, int n) {
double result = 1.0;
boolean negative = false;

if (n < 0) {
negative = true;
n = -n;
}

for (int i = 0; i < n; i++) {

result *= x;
}

return negative ? 1.0 / result : result;

}

// Test the power functions

public static void runTests() {
double base = 2.0;
int[] exponents = {0, 1, 2, 3, 4, 5, -1, -2, -3};

[Link]("Power Function Tests (base = " + base + "):");

[Link]("===========================================");

for (int exp : exponents) {

 double resultSimple = power(base, exp);
double resultOptimized = powerOptimized(base, exp);
double resultIterative = powerIterative(base, exp);
double resultMath = [Link](base, exp);

[Link]("%.2f^%d = %n", base, exp);

[Link](" Simple recursive: %.6f%n", resultSimple);
[Link](" Optimized recursive: %.6f%n", resultOptimized);
[Link](" Iterative: %.6f%n", resultIterative);
[Link](" [Link](): %.6f%n", resultMath);

// Check if all methods agree

if ([Link](resultSimple - resultMath) < 0.000001 &&
[Link](resultOptimized - resultMath) < 0.000001) {
[Link](" ✓ All methods match");
} else {
[Link](" ✗ Discrepancy detected!");
}
[Link]();
}

// Additional test cases

[Link]("\nAdditional Tests:");
[Link]("=================");

double[][] testCases = {
{3.0, 4}, // 3^4 = 81
{5.0, 0}, // 5^0 = 1
{1.5, 3}, // 1.5^3 = 3.375
{0.5, 2}, // 0.5^2 = 0.25
{10.0, -2}, // 10^-2 = 0.01
{0.0, 5}, // 0^5 = 0
{2.0, 10} // 2^10 = 1024
};

for (double[] testCase : testCases) {

double b = testCase[0];
int e = (int) testCase[1];

double result = powerOptimized(b, e);

[Link]("%.2f^%d = %.6f%n", b, e, result);
}
}

// Interactive power calculator

public static void interactive() {
[Link] scanner = new [Link]([Link]);

[Link]("Power Calculator");
[Link]("================");
 while (true) {
[Link]("\nEnter base (or 'q' to quit): ");
String baseInput = [Link]();

if ([Link]("q")) {
break;
}

[Link]("Enter exponent: ");

String expInput = [Link]();

try {
double base = [Link](baseInput);
int exponent = [Link](expInput);

double result = powerOptimized(base, exponent);

[Link]("%.2f^%d = %.6f%n", base, exponent, result);

} catch (NumberFormatException e) {
[Link]("Invalid input. Please enter numeric values.");
}
}

[Link]();
[Link]("Goodbye!");
}

public static void main(String[] args) {

runTests();

// Uncomment for interactive mode

// interactive();
}
}

Python Implementation

def power_simple(x: float, n: int) -> float:

"""Simple recursive power function (O(n))."""
# Base case
if n == 0:
return 1.0

# Handle negative exponent

if n < 0:
return 1.0 / power_simple(x, -n)

# Recursive case
return x * power_simple(x, n - 1)

def power_optimized(x: float, n: int) -> float:

 """Optimized recursive power function (O(log n))."""
# Base cases
if n == 0:
return 1.0

# Handle negative exponent

if n < 0:
return 1.0 / power_optimized(x, -n)

# If exponent is even
if n % 2 == 0:
half = power_optimized(x, n // 2)
return half * half
# If exponent is odd
else:
return x * power_optimized(x, n - 1)

def power_iterative(x: float, n: int) -> float:

"""Iterative power function."""
if n == 0:
return 1.0

result = 1.0
negative = False

if n < 0:
negative = True
n = -n

for _ in range(n):
result *= x

return 1.0 / result if negative else result

def test_power():
"""Test all power functions."""
base = 2.0
exponents = [0, 1, 2, 3, 4, 5, -1, -2, -3]

print("Power Function Tests (base = 2.0):")

print("=================================\n")

for exp in exponents:

simple = power_simple(base, exp)
optimized = power_optimized(base, exp)
iterative = power_iterative(base, exp)
builtin = base ** exp

print(f"{base}^{exp} = ")
print(f" Simple recursive: {simple:.6f}")
print(f" Optimized recursive: {optimized:.6f}")
 print(f" Iterative: {iterative:.6f}")
print(f" Built-in (**): {builtin:.6f}")

# Check if all methods agree

tolerance = 1e-10
if (abs(simple - builtin) < tolerance and
abs(optimized - builtin) < tolerance):
print(" ✓ All methods match")
else:
print(" ✗ Discrepancy detected!")
print()

# Additional test cases

print("\nAdditional Tests:")
print("=================\n")

test_cases = [
(3.0, 4), # 3^4 = 81
(5.0, 0), # 5^0 = 1
(1.5, 3), # 1.5^3 = 3.375
(0.5, 2), # 0.5^2 = 0.25
(10.0, -2), # 10^-2 = 0.01
(0.0, 5), # 0^5 = 0
(2.0, 10) # 2^10 = 1024
]

for base, exp in test_cases:

result = power_optimized(base, exp)
print(f"{base}^{exp} = {result:.6f}")

def interactive():
"""Interactive power calculator."""
print("Power Calculator")
print("================")

while True:
try:
user_input = input("\nEnter base and exponent (e.g., '2 3'), or 'q' to quit: ").strip()

if user_input.lower() == 'q':
print("Goodbye!")
break

parts = user_input.split()
if len(parts) != 2:
print("Please enter exactly two numbers.")
continue

base = float(parts[0])
exponent = int(parts[1])
 result = power_optimized(base, exponent)
print(f"{base}^{exponent} = {result}")

except ValueError:
print("Invalid input. Please enter numeric values.")
except Exception as e:
print(f"Error: {e}")

if __name__ == "__main__":
test_power()

# Uncomment for interactive mode

# interactive()
10. Greatest Common Divisor (GCD)
C Implementation

#include <stdio.h>
#include <stdlib.h>

// Recursive GCD using Euclidean algorithm

int gcd_recursive(int a, int b) {
// Base case: if b is 0, GCD is a
if (b == 0) {
return a;
}

// Recursive case: GCD(a, b) = GCD(b, a % b)

return gcd_recursive(b, a % b);
}

// Iterative GCD using Euclidean algorithm

int gcd_iterative(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}

// Extended Euclidean algorithm (also finds coefficients x, y)

int gcd_extended(int a, int b, int* x, int* y) {
// Base case
if (a == 0) {
*x = 0;
*y = 1;
return b;
}

int x1, y1;

int gcd = gcd_extended(b % a, a, &x1, &y1);
 // Update x and y using results of recursive call
*x = y1 - (b / a) * x1;
*y = x1;

return gcd;
}

// GCD with negative number handling

int gcd(int a, int b) {
// Take absolute values
a = abs(a);
b = abs(b);

// Ensure a >= b for efficiency

if (a < b) {
int temp = a;
a = b;
b = temp;
}

return gcd_recursive(a, b);

}

// LCM (Least Common Multiple) using GCD

int lcm(int a, int b) {
if (a == 0 || b == 0) {
return 0;
}
return abs(a * b) / gcd(a, b);
}

// Test function
void test_gcd() {
int test_cases[][2] = {
{48, 18}, // GCD = 6
{54, 24}, // GCD = 6
{101, 103}, // GCD = 1 (primes)
{0, 5}, // GCD = 5
{5, 0}, // GCD = 5
{0, 0}, // GCD = 0 (defined as 0)
{17, 17}, // GCD = 17
{60, 48}, // GCD = 12
{81, 153}, // GCD = 9
{-48, 18}, // GCD = 6
{48, -18}, // GCD = 6
{-48, -18} // GCD = 6
};

int num_tests = sizeof(test_cases) / sizeof(test_cases[0]);

printf("GCD Tests:\n");
printf("==========\n");

for (int i = 0; i < num_tests; i++) {

int a = test_cases[i][0];
int b = test_cases[i][1];

int result_recursive = gcd_recursive(abs(a), abs(b));

int result_iterative = gcd_iterative(abs(a), abs(b));
int result_gcd = gcd(a, b);

printf("GCD(%d, %d) = \n", a, b);

printf(" Recursive: %d\n", result_recursive);
printf(" Iterative: %d\n", result_iterative);
printf(" With abs(): %d\n", result_gcd);

if (result_recursive == result_iterative &&

result_iterative == result_gcd) {
printf(" ✓ All methods match\n");
} else {
printf(" ✗ Discrepancy detected!\n");
}

// Calculate and print LCM if applicable

if (a != 0 && b != 0) {
int lcm_result = lcm(a, b);
printf(" LCM(%d, %d) = %d\n", a, b, lcm_result);
}

printf("\n");
}

// Test extended Euclidean algorithm

printf("\nExtended Euclidean Algorithm Tests:\n");
printf("===================================\n");

int test_pairs[][2] = {
{48, 18},
{35, 15},
{17, 5}
};

for (int i = 0; i < sizeof(test_pairs) / sizeof(test_pairs[0]); i++) {

int a = test_pairs[i][0];
int b = test_pairs[i][1];
int x, y;

int g = gcd_extended(a, b, &x, &y);

printf("For a=%d, b=%d:\n", a, b);

printf(" GCD = %d\n", g);
 printf(" Coefficients: x = %d, y = %d\n", x, y);
printf(" Verification: %d*(%d) + %d*(%d) = %d\n",
a, x, b, y, a*x + b*y);
printf("\n");
}
}

// Interactive calculator
void interactive_gcd() {
int a, b;

printf("GCD Calculator\n");
printf("==============\n");

while (1) {
printf("\nEnter two integers (or 0 0 to exit): ");

if (scanf("%d %d", &a, &b) != 2) {

printf("Invalid input. Please enter two integers.\n");
while (getchar() != '\n'); // Clear input buffer
continue;
}

if (a == 0 && b == 0) {
printf("Goodbye!\n");
break;
}

int result = gcd(a, b);

printf("GCD(%d, %d) = %d\n", a, b, result);

if (a != 0 && b != 0) {
int lcm_result = lcm(a, b);
printf("LCM(%d, %d) = %d\n", a, b, lcm_result);
}
}
}

int main() {
// Run tests
test_gcd();

// Uncomment for interactive mode

// interactive_gcd();

return 0;
}

Java Implementation

import [Link];
public class GCDCalculator {

// Recursive GCD using Euclidean algorithm

public static int gcdRecursive(int a, int b) {
// Base case
if (b == 0) {
return [Link](a);
}

// Recursive case
return gcdRecursive(b, a % b);
}

// Iterative GCD
public static int gcdIterative(int a, int b) {
a = [Link](a);
b = [Link](b);

while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}

// Extended Euclidean algorithm

public static class ExtendedResult {
public int gcd;
public int x;
public int y;

public ExtendedResult(int gcd, int x, int y) {

[Link] = gcd;
this.x = x;
this.y = y;
}
}

public static ExtendedResult gcdExtended(int a, int b) {

// Base case
if (a == 0) {
return new ExtendedResult(b, 0, 1);
}

// Recursive call
ExtendedResult temp = gcdExtended(b % a, a);
int gcd = [Link];
int x = temp.y - (b / a) * temp.x;
int y = temp.x;
 return new ExtendedResult(gcd, x, y);
}

// LCM using GCD

public static int lcm(int a, int b) {
if (a == 0 || b == 0) {
return 0;
}
return [Link](a * b) / gcdRecursive(a, b);
}

// Run tests
public static void runTests() {
int[][] testCases = {
{48, 18}, // GCD = 6
{54, 24}, // GCD = 6
{101, 103}, // GCD = 1 (primes)
{0, 5}, // GCD = 5
{5, 0}, // GCD = 5
{0, 0}, // GCD = 0
{17, 17}, // GCD = 17
{60, 48}, // GCD = 12
{81, 153}, // GCD = 9
{-48, 18}, // GCD = 6
{48, -18}, // GCD = 6
{-48, -18} // GCD = 6
};

[Link]("GCD Tests:");
[Link]("==========");

for (int[] testCase : testCases) {

int a = testCase[0];
int b = testCase[1];

int resultRecursive = gcdRecursive(a, b);

int resultIterative = gcdIterative(a, b);

[Link]("GCD(%d, %d) = %n", a, b);

[Link](" Recursive: %d%n", resultRecursive);
[Link](" Iterative: %d%n", resultIterative);

if (resultRecursive == resultIterative) {
[Link](" ✓ Methods match");
} else {
[Link](" ✗ Discrepancy detected!");
}

// Calculate LCM if applicable

if (a != 0 && b != 0) {
 int lcmResult = lcm(a, b);
[Link](" LCM(%d, %d) = %d%n", a, b, lcmResult);
}

[Link]();
}

// Test extended Euclidean algorithm

[Link]("\nExtended Euclidean Algorithm Tests:");
[Link]("===================================");

int[][] extendedTests = {
{48, 18},
{35, 15},
{17, 5}
};

for (int[] testCase : extendedTests) {

int a = testCase[0];
int b = testCase[1];

ExtendedResult result = gcdExtended(a, b);

[Link]("For a=%d, b=%d:%n", a, b);

[Link](" GCD = %d%n", [Link]);
[Link](" Coefficients: x = %d, y = %d%n", result.x, result.y);
[Link](" Verification: %d*(%d) + %d*(%d) = %d%n",
a, result.x, b, result.y, a * result.x + b * result.y);
[Link]();
}
}

// Interactive calculator
public static void interactive() {
Scanner scanner = new Scanner([Link]);

[Link]("GCD Calculator");
[Link]("==============");

while (true) {
[Link]("\nEnter two integers (or 'q' to quit): ");

String input = [Link]().trim();

if ([Link]("q")) {
break;
}

String[] parts = [Link](" ");

if ([Link] != 2) {
[Link]("Please enter exactly two integers.");
 continue;
}

try {
int a = [Link](parts[0]);
int b = [Link](parts[1]);

int gcdResult = gcdRecursive(a, b);

[Link]("GCD(%d, %d) = %d%n", a, b, gcdResult);

if (a != 0 && b != 0) {
int lcmResult = lcm(a, b);
[Link]("LCM(%d, %d) = %d%n", a, b, lcmResult);
}

} catch (NumberFormatException e) {
[Link]("Invalid input. Please enter integers.");
}
}

[Link]();
[Link]("Goodbye!");
}

public static void main(String[] args) {

runTests();

// Uncomment for interactive mode

// interactive();
}
}

Python Implementation

import math

def gcd_recursive(a: int, b: int) -> int:

"""Recursive GCD using Euclidean algorithm."""
# Base case
if b == 0:
return abs(a)

# Recursive case
return gcd_recursive(b, a % b)

def gcd_iterative(a: int, b: int) -> int:

"""Iterative GCD using Euclidean algorithm."""
a, b = abs(a), abs(b)

while b != 0:
a, b = b, a % b
 return a

def gcd_extended(a: int, b: int) -> tuple:

"""Extended Euclidean algorithm. Returns (gcd, x, y)."""
# Base case
if a == 0:
return abs(b), 0, 1 if b > 0 else -1

# Recursive call
gcd, x1, y1 = gcd_extended(b % a, a)

# Update x and y
x = y1 - (b // a) * x1
y = x1

return gcd, x, y

def lcm(a: int, b: int) -> int:

"""LCM using GCD."""
if a == 0 or b == 0:
return 0
return abs(a * b) // gcd_recursive(a, b)

def test_gcd():
"""Test all GCD functions."""
test_cases = [
(48, 18), # GCD = 6
(54, 24), # GCD = 6
(101, 103), # GCD = 1 (primes)
(0, 5), # GCD = 5
(5, 0), # GCD = 5
(0, 0), # GCD = 0
(17, 17), # GCD = 17
(60, 48), # GCD = 12
(81, 153), # GCD = 9
(-48, 18), # GCD = 6
(48, -18), # GCD = 6
(-48, -18) # GCD = 6
]

print("GCD Tests:")
print("==========\n")

for a, b in test_cases:
recursive = gcd_recursive(a, b)
iterative = gcd_iterative(a, b)
builtin = [Link](abs(a), abs(b))

print(f"GCD({a}, {b}) = ")

print(f" Recursive: {recursive}")
 print(f" Iterative: {iterative}")
print(f" [Link](): {builtin}")

if recursive == iterative == builtin:

print(" ✓ All methods match")
else:
print(" ✗ Discrepancy detected!")

# Calculate LCM if applicable

if a != 0 and b != 0:
lcm_result = lcm(a, b)
print(f" LCM({a}, {b}) = {lcm_result}")

print()

# Test extended Euclidean algorithm

print("\nExtended Euclidean Algorithm Tests:")
print("===================================\n")

extended_tests = [
(48, 18),
(35, 15),
(17, 5)
]

for a, b in extended_tests:
gcd_result, x, y = gcd_extended(a, b)

print(f"For a={a}, b={b}:")

print(f" GCD = {gcd_result}")
print(f" Coefficients: x = {x}, y = {y}")
print(f" Verification: {a}*({x}) + {b}*({y}) = {a*x + b*y}")
print()

def interactive():
"""Interactive GCD calculator."""
print("GCD Calculator")
print("==============")

while True:
try:
user_input = input("\nEnter two integers (or 'q' to quit): ").strip()

if user_input.lower() == 'q':
print("Goodbye!")
break

parts = user_input.split()
if len(parts) != 2:
print("Please enter exactly two integers.")
continue
 a = int(parts[0])
b = int(parts[1])

gcd_result = gcd_recursive(a, b)
print(f"GCD({a}, {b}) = {gcd_result}")

if a != 0 and b != 0:
lcm_result = lcm(a, b)
print(f"LCM({a}, {b}) = {lcm_result}")

except ValueError:
print("Invalid input. Please enter integers.")
except Exception as e:
print(f"Error: {e}")

if __name__ == "__main__":
test_gcd()

# Uncomment for interactive mode

# interactive()