9.26递归函数

递归函数的定义和格式

递归是一种常用的解决问题的方法，特别适用于解决可以被分解为类似子问题

//递归函数：在函数内部再次调用自己
//解决可以被分解为类似子问题的问题
//组成：
//1.基本情况 最小问题的答案
//2.递归情况 调用自己去解决子问题
object TestFucRecursive {
//  def fn(): Unit = {
//    println("fn...")
//    fn()
//  }
//定义一个函数，求1-n的和
//  def sum(n:Int):Int = {
//  var s = 0
//  for(i <- 1 to n){
//    s += i
//  }
//  s
//}
  //定义一个递归函数，求1-n的和
  def sum(n:Int):Int = {
  println(n)
  //1.基本情况：最小问题，直接给答案，阻止死循环
  if (n == 1){
    1
  }else{
    //2.递归情况：再次调用自己去解决子问题
    return n + sum(n-1)
  }
}

  def main(args: Array[String]): Unit = {
    var s = sum(10)
    println(s)
  }
}

  //定义一个递归函数，求1-n的和
//  def sum(n:Int):Int = {
//  println(n)
//  //1.基本情况：最小问题，直接给答案，阻止死循环
//  if (n == 1){
//    1
//  }else{
//    //2.递归情况：再次调用自己去解决子问题
//    return n + sum(n-1)
//  }
//}

//  def main(args: Array[String]): Unit = {
//    var s = sum(10)
//    println(s)
//  }
  //定义一个函数，求1*2*3*4*...*n
  def mul(n:Int):Int = {
    if (n == 0){
      1
    }else{
      mul(n-1) * n
    }
  }

  def main(args: Array[String]): Unit = {
    var s = mul(5) //5*4*3*2*1 = 120
    println(s)
  }
}

斐波那契数列

斐波那契数列的定义是：

基本情况：f(0) = 0,f(1) = 1

递归情况：f(n) = f(n-1) + f(n-2) (当n>= 2）。求它的第n项。

  //定义一个函数，计算斐波那契数列的第n项
  //斐波那契数列：1 1 2 3 5 8 13 21 ...
  //规律：
  //1.基本情况：f(0) = 0,f(1) = 1
  //2.递归情况：f(n) = f(n-1) + f(n-2)
  def feb(n:Int):Int ={
    //1.基本情况
    if (n == 0)
      0
    else if (n == 1)
      1
      else
      feb(n-1) + feb(n-2)
  }

  //定义一个函数，打印多位数字的各个位数上的数字 - 拆数
  def f(n: Int): Unit ={//n = 1234 ---->1 2 3 4
    //1.基本情况 假设数字只有1位，直接输出
    if (n < 10){
      print(n)
    }else{
      //（1）输出除了尾数之外的数字
      f(n/10)
      //（2）输出尾数
      println(n%10)
    }
  }

  def main(args: Array[String]): Unit = {
    f(45)
  }
}