C语言中的递归函数如何工作

Question

函数 fun(n) 的定义如下：

fun(n) = 1                 (if n <=1)
fun(n) = fun(n/2)          (if n is even)
fun(n) = 2*fun((n-1)/3)    (if n> and n is odd)

我想写一个递归函数来计算并返回结果。我刚刚开始学习递归，我在编写这个函数时有些迷茫。能否有人纠正我并解释一下吗？谢谢！

以下是我的代码：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h> 
#include <math.h>

int fun(int n);

int main()
{
    int num;

    printf("\nEnter a number: ");
    scanf("%d", num);
    printf("Result = %d\n", fun(num));
    return 0;
}

int fun(int n)
{
    if (n <= 1)
    {
        return 1;
    }

    else if (n % 2 == 0)
    {
        return fun(n / 2);
    }

    else if ((n > 1) && (n % 2 == 0))
    {
        return 2 * fun((n - 1) / 3);
    }
}

期望输出：

Enter a number: 13
Result = 2

Enter a number: 34
Result = 4

我得到的输出结果：

Enter a number: 13
Result = 1

Enter a number: 34
Result = 1

- unintendedjoy

---

在输入 scanf("%d", num); 时，你是否忘记了在 num 前面加上 &？ - haccks

学习递归，然后“忘记”它。通常最好使用循环。 - Bathsheba

你的第三个条件应该是 else if ((n > 1) && (n % 2 != 0)) 而不是 else if ((n > 1) && (n % 2 == 0))。 - Aliou

@Aliou 第三个条件难道不应该简单地是 else（或者根本就没有 else，只有那里的主体）吗？所有其他可能性已经被排除了。 - mah

@mah 是的，你说得对。 - Aliou

Answer 1

scanf将指向int的指针作为%d的参数，即

scanf("%d", &num);

此外，你的函数 fun 未能处理所有情况，可能会出现错误：

if (n <= 1)
{
    return 1;
}
else if (n % 2 == 0)
{
    return fun(n / 2);
}
else if ((n > 1) && (n % 2 == 0))
{
    return 2 * fun((n - 1) / 3);
}

最后的 else if 条件永远不会被满足，因为前面对 n % 2 == 0 的检查已经在那种情况下返回了。此外，n > 1 是无意义的，因为第一个 n <= 1 在所有其他情况下都返回。您可以简单地这样写：

else
{
    return 2 * fun((n - 1) / 3);
}

- Arkku

Answer 2

罪魁祸首是最后一个else if条件。请将其更改为：

else if ((n % 2) != 0)

- Green goblin

---

或者完全删除else，因为所有其他条件已经被检查并拒绝。 - mah

Answer 3

我认为最后一个 if 应该是：

else if ((n > 1) && (n % 2 != 0))

注意使用 != 而不是 ==。

- ctutte

Answer 4

这里写错了n为奇数的条件。你写的与n为偶数时相同。

最好明确地使情况不重叠，这样您就可以始终返回并且没有警告，像这样：

int fun(int n)
{
    if(n <= 1)
        return 1;
    if(n % 2 == 0)
        return fun(n/2);
    //No need for a condition, we know the last one must be satisfied
    return 2 * fun((n-1)/3);
}

或者，添加另一个“默认”情况，表示出现了某些错误。

- Steve Cox

Answer 5

第三个条件

else if ((n > 1) && (n % 2 == 0))

这是错误的，但是你没有修复它，而是使用了else而不是else if - 因为所有其他条件已经被检查过了。

- Wojtek Surowka