递归算法学习

  1. package com.example.interview.augom;
  3. //递归算法学习
  4. public class test1 {
  5.     public static void main(String[] args) {
  6.         //斐波那契数列
  7.         int i = 1;
  8.         for (i = 1; i <= 20; i++) {
  9.             System.out.println("兔子第" + i + "个月的总数为:" + f(i));
  10.         }
  11.         //1……到100的和
  12.         System.out.println(new test1().num100(10));
  13.         //阶乘
  14.         System.out.println(new test1().fact(3));
  15.     }
  17.     public int numT(int i) {
  18.         System.out.print(i);
  19.         i--;
  20.         //结束条件
  21.         if (i <= 0) {
  22.             return 0;
  23.         }
  24.         return numT(i);
  26.     }
  28.     //1……100
  29.     public int num100(int i) {
  30.         if (i == 1) {
  31.             return 1;
  32.         } else
  33.             return i + num100(i - 1);
  35.     }
  36.     //斐波那契数列
  37.     public static int f(int x) {
  38.         //条件
  39.         if (x == 1 || x == 2) {
  40.             return 1;
  41.         } else
  42.             //递归满足的函数是这个
  43.             return f(x - 1) + f(x - 2);
  45.     }
  46.     //阶乘
  47.     public int fact(int i) {
  48.         if (i == 1) {
  49.             return 1;
  50.         } else {
  51.             return i * fact(i - 1);
  52.         }
  53.     }
  55. }

递归学习网站

什么是递归？

递归，在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。简单来说，递归表现为函数调用函数本身。在知乎看到一个比喻递归的例子，个人觉得非常形象，大家看一下：

递归最恰当的比喻，就是查词典。我们使用的词典，本身就是递归，为了解释一个词，需要使用更多的词。当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词，可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。

来试试水，看一个递归的代码例子吧，如下：

  1. public int sum(int n) {
  2.     if (n <= 1) {
  3.         return 1;
  4.     } 
  5.     return sum(n - 1) + n; 
  6. }

递归的特点

实际上，递归有两个显著的特征,终止条件和自身调用:

  • 自身调用：原问题可以分解为子问题，子问题和原问题的求解方法是一致的，即都是调用自身的同一个函数。
  • 终止条件：递归必须有一个终止的条件，即不能无限循环地调用本身。

递归解题思路

解决递归问题一般就三步曲，分别是：

  • 第一步，定义函数功能
  • 第二步，寻找递归终止条件
  • 第二步，递推函数的等价关系式

这个递归解题三板斧理解起来有点抽象，我们拿阶乘递归例子来喵喵吧~

  1. package com.example.interview.augom;
  3. //递归算法学习
  4. public class test1 {
  5.     public static void main(String[] args) {
  6.         //斐波那契数列
  7.         int i = 1;
  8.         for (i = 1; i <= 20; i++) {
  9.             System.out.println("兔子第" + i + "个月的总数为:" + f(i));
  10.         }
  11.         //1……到100的和
  12.         System.out.println(new test1().num100(10));
  13.         //阶乘
  14.         System.out.println(new test1().fact(3));
  15.     }
  17.     public int numT(int i) {
  18.         System.out.print(i);
  19.         i--;
  20.         //结束条件
  21.         if (i <= 0) {
  22.             return 0;
  23.         }
  24.         return numT(i);
  26.     }
  28.     //1……100
  29.     public int num100(int i) {
  30.         if (i == 1) {
  31.             return 1;
  32.         } else
  33.             return i + num100(i - 1);
  35.     }
  36.     //斐波那契数列
  37.     public static int f(int x) {
  38.         //条件
  39.         if (x == 1 || x == 2) {
  40.             return 1;
  41.         } else
  42.             //递归满足的函数是这个
  43.             return f(x - 1) + f(x - 2);
  45.     }
  46.     //阶乘
  47.     public int fact(int i) {
  48.         if (i == 1) {
  49.             return 1;
  50.         } else {
  51.             return i * fact(i - 1);
  52.         }
  53.     }
  55. }