时间戳

首页 > 解决方案 > 递归函数背后的魔力是什么？

c - 递归函数背后的魔力是什么？

问题描述

问题：

你能解释一下这个函数如何返回正确的结果16吗？
我是编程新手，现在这段代码是递归的，但是我想我迷失了，就像我理解它们一样。尽管如此，我相信我会弄清楚阶乘递归或斐波那契递归。

基础是0，这很好，但我不知道为什么会得到16......
我在函数中打印了每个变量并进行了调试，但这些除了麻烦之外没有帮助。当bvariable is 0（和avariable is 32）时，条件得到满足，但为什么它返回 value 16？我会像经典的阶乘函数示例那样理解一种函数n * fact(n-1)，但在这里我无法想象递归如何返回预期结果。

代码：

#include <stdio.h> 
  
int fun(int a, int b)  
{ 
   if (b == 0) 
    {
       return 0; 
    }
   if (b % 2 == 0) 
    {
    return fun(a+a, b/2);
    }
   return fun(a+a, b/2)+a;
} 
  
int main() 
{ 
  printf("%d\n", fun(4, 4)); 
  return 0; 
}

提前致谢！

标签： crecursion

解决方案

添加打印输出，它会变得非常清晰：

int fun(int a, int b)
{
    printf("fun(%d, %d)\n", a, b);
    if (b == 0) {
         printf("b == 0, returning 0\n");
         return 0;
    }
    if (b % 2 == 0) {
        printf("b is even, returning f(%d, %d)\n", a+a, b/2);
        return fun(a+a, b/2);
    }
    printf("b is odd, returning f(%d, %d) + %d\n", a+a, b/2, a);
    return fun(a+a, b/2)+a;
}

输出：

$ ./a.out 
fun(4, 4)
b is even, returning f(8, 2)
fun(8, 2)
b is even, returning f(16, 1)
fun(16, 1)
b is odd, returning f(32, 0) + 16
fun(32, 0)
b == 0, returning 0
16

所以最终发生的事情是f(16, 1)返回f(32, 0) + 16并f(32, 0)计算为零，所以16返回。

您也可以这样做，但请注意，这将改变输出的顺序，因为打印输出需要等待返回：

int fun(int a, int b)  
{ 
    printf("fun(%d, %d)\n", a, b);
    if (b == 0) {
        printf("b == 0, returning 0\n");
        return 0; 
    }
    if (b % 2 == 0) {
        int ret = fun(a+a, b/2);
        printf("b is even, returning f(%d, %d) = %d \n", a+a, b/2, ret); 
        return ret; //fun(a+a, b/2);
    }
    int ret = fun(a+a, b/2) + a;
    printf("b is odd, returning f(%d, %d) + %d = %d \n", a+a, b/2, a, ret);
    return ret;
}

输出：

$ ./a.out 
fun(4, 4)
fun(8, 2)
fun(16, 1)
fun(32, 0)
b == 0, returning 0
b is odd, returning f(32, 0) + 16 = 16 
b is even, returning f(16, 1) = 16 
b is even, returning f(8, 2) = 16 
16

理解递归的一个好方法是使用笔和纸来了解为什么在这些情况下打印输出的顺序如此不同。但我把它留给你。

推荐阅读