取法其上,得乎其中

学习使用递归算法

性质

主要性质为通过不停的运行自己本身达到循环的目的。

简单的递归:

 public static int f(int i){
  int n=1;
  if (i==0) {
   return n;
  }
  return i*f(i-1);
 }


通过递归计算阶乘的例子,f(5)输出结果为120。
通过例子可以简单的了解到,递归的构造有一个退出条件(r==0),一条调用自身的代码。
为了方便理解,先编写一份使用For循环达到计算阶乘目的的代码:

int n=1; 
for (int i = 5; i>0; i--) {
    n*=i;
}
System.out.println(n);

我们都知道阶乘就是5*4*3*2*1式子进行计算,我们只需要通过1*n-1就可以完成。
因为递归的性质,方法本身会被无限循环,所以这个时候我们需要一个退出条件,根据以上阶乘例子可以看出,每一计算阶乘的式子的最后一步都是*1,所以我们可以使用i>1/i==0,这些式子进行判断。

然后剩余的一个就是要执行的指令和调用自己本身。

简单的来说,我们可以把下面这个调用的F函数想象成另外一个并不相同的函数。
假设n=5。那么n*f(n-1)=5*f(4),也就是说,在当前函数F的基础上,又调用了一个跟F一样的函数。
当前的n是5,它要乘以要调用的函数,而要调用的函数里是4..以此类推就是5*4*3*2*1,当执行f(0)的时候,通过前面的递归例子可以看出,接下来就不会继续调用自己。

字符串翻转

public static String f1(String s){
  if (s.length()==1) {
   return s;
  }
  return s.charAt(s.length()-1)+f1(s.substring(0, s.length()-1));
 }


整体思路流程:
假设s=abc,那么s的大小是3,使用charAt函数获取3-1位置的字符串,也就是c,
然后再次调用f1函数,传入的内容是,s的0——2(s大小减去1)范围的内容,也就是bc。bc再进行运算,大小为2,取出位置1的字符串(b),
调用f1函数,参数为0——1范围字符串,大小为1,触发IF,返回S,这里方法中的S参数,只有一个c(每一个方法都是单独开辟的内存空间,并不是之前的那个S,而是上一层传进来的参数S)。

斐波那契数列

 public static int f(int n){
  if (n==3) {   
   return 2;
  }
  if (n<3) {
   return 1;
  }
 return f(n-1)+f(n-2);
 }


斐波那契数列的定义为,当前数为前两位相加而成。1 1 2 3 5 8 13 21....
根据样例发现,前两位并不符合这个定义,所以我们使用<3进行判断处理。而退出条件以==3做处理。
然后根据f(n)=f(n-1)+f(n-2)的公式进行计算。

学习使用递归算法

https://ku-m.cn/index.php/archives/18/

作者

KuM

发布时间

2019-09-23

许可协议

CC BY 4.0

添加新评论