求指导一道C语言程序题

Question

代码如下：

main()
{ int x;
  fib(7, &x);
  printf("\nx=%d\n", x);
}
fib(int n, int *s)
{ int f1, f2;
  if(n == 1 || n==2 ) *s = 1;
  else { fib( n-1, &f1);
            fib( n-2, &f2);
          *s = f1 + f2; }
}

知道是求斐波纳契数列，但是不能理解求解的过程，求一个详细的指导说明（平时看的都是不用指针求的版本）

Answer 1

这个程序之所以用指针，主要是为了节约内存，它不是通过返回值返回fib(n)，而是通过s，这样上一层递归无需再开辟新的变量
好比，如下程序定义了一个add函数

#include <stdio.h>
int add(int a, int b);
int main()
{
    int s = add(1, 1);
    printf("1+1=%d\n", s);
}
int add(int a, int b)
{
    return a + b;
}

它也可以写成

#include <stdio.h>
void add(int a, int b, int *s);
int main()
{
    int s;
    add(1, 1, &s);
    printf("1+1=%d\n", s);
}
void add(int a, int b, int * s)
{
    *s = a + b;
}

这两者其实是一回事。

你的程序如下：

#include <stdio.h>
void fib(int n, int *s);
int main()
{ int x;
  fib(7, &x);
  printf("\nx=%d\n", x);
}
void fib(int n, int *s)
{ int f1, f2;
  if(n == 1 || n==2 ) *s = 1;
  else { fib( n-1, &f1);
            fib( n-2, &f2);
          *s = f1 + f2; }
}

它其实是

#include <stdio.h>
int fib(int n);
int main()
{ int x;
  x = fib(7);
  printf("\nx=%d\n", x);
}
int fib(int n)
{ int f1, f2;
  if(n == 1 || n==2 ) return 1;
  else { f1 = fib( n-1);
         f2 = fib( n-2);
          return f1 + f2; }
}

再简化下

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

这其实就是数学归纳法对斐波拉契数列的定义
fib(n) = 1 ... 当 n = 1或者2时
fib(n) = fib(n - 2) + fib(n - 1) ... 当n > 2时
也就是说斐波拉契数列是这样一种数列，第一项第二项是1，第三项开始，每一项是前两项之和。