如何找到递归函数调用自身的次数？

Question

考虑以下递归 C 函数。

 void get (int n) { 
    if (n<1) return; 
    get (n-1) ; 
    get (n-3) ; 
    printf ("%d", n) ; 
    }

如果 get(6) 函数在 main() 中被调用，那么 get() 函数在返回主 0 之前会被调用多少次？

Answer 1

要计算您的函数被调用了多少次，请在每次输入函数时递增一个静态计数器，并在调用后打印出该值。例如：

int counter;
void get (int n) { 
    ++counter; /* increment counter before first return */
    if (n<1) return; 
    get (n-1) ; 
    get (n-3) ; 
    printf ("%d", n) ; 
}

int main()
{
    counter = 0; /* reset counter before each use */
    get(6);
    printf("get() was called %d times\n", counter);
}

Answer 2

考虑到这当然是一个学术练习，您可能需要了解递归的工作原理。

我们可以修改您的代码以打印出调用树，显示每次调用：

#include <stdio.h>

void get(int n, int depth)
{ 
    static int call = 1;
    printf("%3d: %*sget(%d)\n", call++, 2*depth, "", n); 
    if (n<1)
        return; 
    get(n-1, depth+1); 
    get(n-3, depth+1); 
}

int main(void)
{
    get(6, 0);
    return 0;
}

输出：

  1: get(6)
  2:   get(5)
  3:     get(4)
  4:       get(3)
  5:         get(2)
  6:           get(1)
  7:             get(0)
  8:             get(-2)
  9:           get(-1)
 10:         get(0)
 11:       get(1)
 12:         get(0)
 13:         get(-2)
 14:     get(2)
 15:       get(1)
 16:         get(0)
 17:         get(-2)
 18:       get(-1)
 19:   get(3)
 20:     get(2)
 21:       get(1)
 22:         get(0)
 23:         get(-2)
 24:       get(-1)
 25:     get(0)

请注意，我假设您的分配状态为 if (n<1) ("one")，而不是 if (n<l) ("ell")。另外，请注意我添加了一个 depth 参数。这使我能够适当地缩进每个调用。

Answer 3

我们可以对上述函数做一个递归关系为：

T(n) = T(n-1)  +  T(n-3) + 2

T(n)=1 for n<=0

我在等式中添加了 2，因为我们调用了两次递归函数。

首先将 n=1 替换为 n=6，您将得到答案 25

如何找到递归函数调用自身的次数？

How can I find number of times a recursive function calls itself?

c

recursion