[アルゴリズム]再帰

3483 ワード
復帰する python アルゴリズム#アルゴリズム# swift テキストリンク

復帰(Recursion)

  • 同じ関数を関数内で呼び出す

    • 例

  • 工場(!)救い
  • 回文:逆さまに読んでも読める単語、数字など

    • 実施例（工場）

  • 関数factorial(n)殷n!n!n! 返すと言って
  • 数学の授業でf(n)f(n)=n!n!n! 考えたら
  • 2! = 1 ×\times× 2 = factorial(2)
  • 3! = 1 ×\times× 2 ×\times× 3
  • = factorial(2) ×\times× 3
  • = factorial(3)
  • 4! = 1 ×\times× 2 ×\times× 3 ×\times× 4
  • = factorial(2) ×\times× 3 ×\times× 4
  • = factorial(3) ×\times× 4
  • = factorial(4)

    • 一般化

  • n! = factorial(n-1) ×\times× n

    • n/a.結論

  • factorial(n) = factorial(n-1) ×\times× n
  • factorial(n)関数はfactorial(n-1)×\times× 返却のみn
  • n <= 1の場合は1を返却します.(0!定義は1)

    • 特長

  • 徐々に小さくなる仕組み
  • いつか終わる
  • 再帰はスタック(LIFO)

  • ex4!4!4!ここから積み上げ4×\times× f(3)f(3)f(3)4 ×\times× f(3)f(3)f(3)3 ×\times× f(2)f(2)f(2)4 ×\times× f(3)f(3)f(3)3 ×\times× f(2)f(2)f(2)2 ×\times× f(1)f(1)f(1)f(1)f(1)=1 f(1)=1 f(1)=1ここから4を減算×\times× f(3)f(3)f(3)3 ×\times× f(2)f(2)f(2)2 ×\times× 14 ×\times× f(3)f(3)f(3)3 ×\times× 24 ×\times× 6 === 24

    • Python

    def factorial(n):
    if n > 1:
        return factorial(n-1) * n
    else:
    	return 1

    Swift

    func factorial(_ n: Int) -> Int {
    if n > 1 {
        return factorial(n-1) * n
    } else {
    	return 1
    }
}
    Typescript Class
    白駿5543号(出勤日)解答