What is the implementation principle and optimization techniques for recursive functions in C language?

What is the implementation principle and optimization techniques for recursive functions in C language?

Recursive Function Principles:

1. Basic Structure

   c
   // Three elements of recursive functions
   // 1. Base case (termination condition)
   // 2. Recursive call
   // 3. Progress toward base case
   
   int factorial(int n) {
       if (n <= 1) {  // Base case
           return 1;
       }
       return n * factorial(n - 1);  // Recursive call
   }

2. Call Stack Mechanism

   c
   void recursive_function(int n) {
       if (n <= 0) return;
       
       // Each call creates a new stack frame
       // Stores local variables, return address, etc.
       printf("Before: %d\n", n);
       recursive_function(n - 1);
       printf("After: %d\n", n);
   }

Classic Recursive Examples:

1. Fibonacci Sequence

   c
   // Basic version (inefficient)
   int fibonacci(int n) {
       if (n <= 1) return n;
       return fibonacci(n - 1) + fibonacci(n - 2);
   }
   
   // Optimized version (memoization)
   int fib_memo(int n, int *memo) {
       if (n <= 1) return n;
       if (memo[n] != -1) return memo[n];
       memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
       return memo[n];
   }

2. Binary Search

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

3. Quick Sort

   c
   void quick_sort(int arr[], int low, int high) {
       if (low < high) {
           int pi = partition(arr, low, high);
           quick_sort(arr, low, pi - 1);
           quick_sort(arr, pi + 1, high);
       }
   }

Optimization Techniques:

1. Tail Recursion Optimization

   c
   // Normal recursion
   int factorial(int n) {
       if (n <= 1) return 1;
       return n * factorial(n - 1);
   }
   
   // Tail recursive version
   int factorial_tail(int n, int accumulator) {
       if (n <= 1) return accumulator;
       return factorial_tail(n - 1, n * accumulator);
   }
   
   // Call method
   int result = factorial_tail(5, 1);

2. Memoization Technique

   c
   #define MAX_N 1000
   int memo[MAX_N];
   
   int fibonacci_optimized(int n) {
       if (n <= 1) return n;
       if (memo[n] != 0) return memo[n];
       return memo[n] = fibonacci_optimized(n - 1) + fibonacci_optimized(n - 2);
   }

3. Recursion to Iteration

   c
   // Recursive version
   int sum_recursive(int n) {
       if (n <= 0) return 0;
       return n + sum_recursive(n - 1);
   }
   
   // Iterative version
   int sum_iterative(int n) {
       int sum = 0;
       for (int i = 1; i <= n; i++) {
           sum += i;
       }
       return sum;
   }

Important Considerations:

1. Stack Overflow Risk

   c
   // Dangerous: Deep recursion may cause stack overflow
   int deep_recursion(int n) {
       if (n <= 0) return 0;
       return deep_recursion(n - 1);
   }

2. Performance Considerations

   • Recursion has function call overhead
   • May involve repeated calculations
   • High stack space consumption

3. Applicable Scenarios

   • Tree and graph traversal
   • Divide and conquer algorithms
   • Dynamic programming
   • Backtracking algorithms