递归总结

总结一下今天学习的递归产生的感悟

递归细分成三种类型：

1.求第n项值

2.求第（n-1）项加第（n-2）项等于第n项（斐波那契数列）

3.求前n项和

1.求第n项值：

如同高中的函数通项公式，观察数列，找出递推公式。

找第n项和第（n-1）项的关系；

找出口。

按照先写出口再写递推关系的顺序书写函数。

例如1,2,3，，，，n

找出递推公式：

f（n）=f（n-1）+1

找到出口：

f（1）=1；

联立即为递归函数

f（n）=f（n-1）+1

f（1）=1

书写函数如下：

int f(int n)
{
    if(n==1)
        return 1;
    else
        return(   f(n-1)+1   )//此处f（n）=f（n-1）+1，只用写等号后部分即可
}

2.求第（n-1）项加第（n-2）项等于第n项

方法同上

先找递推关系

再确定出口。

例如斐波那契数列

1,1,2,3,5,8,13,21,34......

递推关系：

f（n）=f(n-1)+f(n-2)

找出口：

f(1)=1

f(2)=1

将上述联立即为递归公式：

f（n）=f(n-1)+f(n-2)

f(1)=1

f(2)=1

成代码如下：

int f(int n)
{
  if(x==1）
     return 1;
     
  else if(x==2)
     return 1;
     
  else
     return (   f(n-1)+f(n-2)   )
     
}

3.求前n项和：

方法同上

例如求1+2+3+4+....+n

设f(n)=1+2+3+...+n

那么sum（n）=f（n-1）+n

尝试求1+2+3+4+...+100

已知结果为5050

找递推公式：

f(n)=f(n-1)+n;

f(1)=1;

sum(n)=sum(n-1)+f(n);

sum(1)=1;

int SUM(int x)
{
    int a;
    int f(int n)
    {
        if(n==1)
            return 1;
        else
            return (f(n-1)+n);
    }

    if(x==1)
    {
        return 1;
    }
    else
    {
        return (SUM(x-1)+f(x));
    }
}