C中的递归函数

Question

我把这段代码作为我学校的练习:

#include <stdio.h>

main()
{
    int unknown(int a, int b)
    {
        if (b == 1) 
            return a;
        else 
            return a + unknown(a, b - 1);
    }
    printf("Value = %i", unknown(3, 4));
}

结果是"价值= 12".我似乎无法理解为什么.AFAIK它应该是a = 3,b = 4然后是3 + 4,对吧？

Answer 1

关键是除非b== 1,unknown()调用unknown()- 这称为递归.

为简洁起见,我将调用函数f而不是未知函数:

有些语言使用模式匹配以更清晰的方式呈现这样的函数; 假想模式匹配语言中的等价物可能是:

f(x,1) := x
f(x,y) := x + f(x,y-1)

所以...

f(3,4) = 3 + f(3, 4-1)
       = 3 + f(3, 3)
       = 3 + ( 3 + f(3, 3-1))
       = 3 + ( 3 + f(3, 2))
       = 3 + ( 3 + ( 3 + f(3, 2 - 1)))
       = 3 + ( 3 + ( 3 + f(3, 1)))
       = 3 + ( 3 + ( 3 + (3)))
       = 12

我想你的功课是决定这个功能的名字比"未知"更好.一旦你决定,请注意递归不是实现该函数的最佳方式,除非你的语言特别支持一种称为尾递归优化的特性(这可能是你想要稍后搁置的主题).

此外,其他人已经注意到C中不允许嵌套函数 - 即使您的特定编译器可能会处理它们.这意味着虽然您的程序执行此操作:

 int function1() {
     int function2(int x) {
         ...
     }
     int x = function2(3);
 }

...标准的C编译器不允许它.通常的方法是:

 int function1() {
     int x = function2(3);
 }

 int function2(int x) {
     ...
 }