简单了解递归函数

什么是递归?什么情况下会使用递归?

  1. 递归作为一种算法在程序设计语言中广泛使用,是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象。
  2. 递归算法一般用于解决三类问题
    • 数据的定义是按递归定义的。(Fibonacci 函数)
    • 问题解决按递归算法实现。(回溯)
    • 数据的结构形式是按递归定义的。(树的遍历,图的搜索)
  3. 下面两个程序是使用递归实现的小栗子

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    /**
    * 计算二进制中1的个数
    * N为奇数,二进制中的1的个数等于N/2的个数
    * 例子
    * num =13
    * 1. getBinary(13/2=6)+1;
    * 2. getBinary(6/2=3)+1;
    * 3. getBinary(3/2=1)+1+1;
    * 4. getBinary(1)+1+1; getBinary(1) 返回1,所以与后面两个1相加是3
    **/
    public static int getBinary(int num){
    if (num == 1)
    return 1;
    if (0 == num%2){
    // 为偶数
    return getBinary(num/2);
    } else {
    return getBinary(num/2)+1;
    }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    /**
    * 求 n!
    *
    **/
    public class Factorial {
    public static void main(String[] args) {
    long n = 7;
    System.out.println();
    }
    public static long doFactorial(long n) {
    if (n < 1) {
    System.out.println("error");
    return 0;
    } else if (n == 1 || n ==2 ) {
    return n;
    } else {
    return n * doFactorial(n-1);
    }
    }
    }
-------------本文结束感谢您的阅读-------------
Thank you for your encouragement