递归的思想与应用

前言

递归是一种数学上分而自治的思想,将原问题分解为规模较小的问题进行处理,分解后的问题与原问题的类型完全相同,但规模较小,通过小规模问题的解,能够轻易求得原问题的解,但是问题的分解是有限的,当边界条件满足时,递归结束直接求解否则递归继续进行,在程序设计中递归函数就是递归的体现,递归模型的一般表示法如下

递归思想的应用
1.求解:Sum(n) = 1 + 2 + 3 +…+ n

#include <stdio.h>
#include <stdlib.h>
unsigned int sum(unsigned int n)
{ 
   int a;
   if(n>1)
   { 
     return n+sum(n-1);
   }
   else
   {
      return 1;
   }
}
int main()
{
   unsigned int b = sum(100);
   printf("%d\n",b);
}

结果:

5050

2.求解斐波拉系数列
数列自身递归定义:1,1,2,3,5,8,13,21…

#include <stdio.h>
#include <stdlib.h>
unsigned int func(unsigned int n)
{
   if(n>2)
   {
     return func(n-1)+func(n-2);
   }
   if(n==2||(n==1))
   {
     return 1;
   }
}
int main()
{  
   int i = 1;
   for( i = i;i<=10;i++)
   {
     printf("%d ,",func(i));
   }
}

结果:

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

3.递归求解字符串长度

#include <stdio.h>
#include <stdlib.h>
int  mystrlen(char *s)
{
    if(*s != '\0')
    {
       return  1+strlen(s+1);
    }
    if(*s=='\0')
    {
         return 0;
    }
}
int main()
{
  printf("%d\n",mystrlen("cgshappy"));
}

结果:

[e-mail]:~$ ./a.out 
8

可以看出用递归解决问题首先要建立递归的模型,递归解法必须有边界条件,否则无解,不要陷入递归函数的执行细节,学会通过代码描述递归问题