如何编写任意递归函数的递推式？求通用方法及实例推导

Hey there! I totally get where you're coming from—staring at recursive functions and trying to formalize their recurrence relations can feel like cracking a code at first, but once you break down the pattern step by step, it clicks. Let’s walk through your examples to build that intuitive process you’re missing.

General Step-by-Step Flow #

Before diving into the code, here’s a simple framework to follow every time:

1. Spot the base cases: These are the stopping points where no recursion happens—they give you the "starting values" for your recurrence.
2. Analyze the recursive step: Ask, "What does the function do when it’s not in the base case?" How many recursive calls does it make? Are there any operations (like arithmetic, printing) that happen alongside the recursion?
3. Translate to math: For functions that return a value, the recurrence will directly mirror the return logic. For counting operations (like time complexity), count each non-recursive step and add the cost of the recursive calls.

Example 1: void print(int n) #

void print(int n) { 
  if (n>0) {
    cout<< n<<endl; 
    print(n-1);
  } 
}

Let’s define T(n) as the number of print operations the function performs for input n:

• Base case: When n ≤ 0, the function does nothing. So T(n) = 0 for n ≤ 0.
• Recursive case: When n > 0, we print once, then recurse on n-1. So T(n) = 1 + T(n-1) for n > 0.

Example 2: int power(int x, int n) #

int power(int x, int n) { 
  if (n==0) return 1; 
  else return x * power(x, n-1); 
}

First, let’s look at the return value recurrence (let’s call it P(n) which represents x^n):

• Base case: When n=0, P(n) = 1.
• Recursive case: For n > 0, P(n) = x * P(n-1) (since we multiply x by the result of the recursive call to power(x, n-1)).

If we’re talking about time complexity (counting multiplications), let T(n) be the number of multiplication operations:

• T(0) = 0 (no multiplication needed for the base case)
• T(n) = 1 + T(n-1) for n > 0 (one multiplication plus the cost of the recursive call).

Example 3: int fib(int n) #

int fib(int n) { 
  if (n==0 || n==1) return 1; 
  else return fib(n-1) + fib(n-2); 
}

This is a classic recursive Fibonacci function (with a slight twist—usually Fib starts with fib(0)=0, but here both base cases return 1). Let F(n) be the value returned by fib(n):

• Base cases: F(0) = 1 and F(1) = 1.
• Recursive case: For n ≥ 2, F(n) = F(n-1) + F(n-2) (the function adds the results of the two smaller subproblems).

Example 4: int numberofDigits(int n) (completed) #

Your code cuts off, but this is a common function. Let’s assume the full logic is:

int numberofDigits(int n) { 
  if ((-10 < n) && (n < 10)) return 1; 
  else return 1 + numberofDigits(n / 10); 
}

Let D(n) be the number of digits in n:

• Base case: When n is a single digit (|n| < 10), D(n) = 1.
• Recursive case: For multi-digit numbers, we count 1 digit plus the number of digits in n/10 (integer division removes the last digit). So D(n) = 1 + D(n/10) for |n| ≥10.

Key Takeaways #

The biggest thing to remember is that recurrence relations are just a mathematical way to write down what the recursive function is already doing. If you can describe in plain English what the function does at each step, translating that to math becomes straightforward.

内容的提问来源于stack exchange，提问作者Jawwad Rafiq