再帰とは？

Pythonでコーディング面接問題を練習する

Kirill Smirnov

Data Science Consultant, Altran

定義

再帰は、問題をそれ自体で定義する手法です
再帰は、関数が自分自身をサブルーチンとして呼ぶ処理です

例：階乗 $n!$

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1$

$n = 4$:

$4! = 4\cdot3\cdot2\cdot1$

4! = 24

階乗 - 反復法

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1 = $

$ = 1\cdot2\cdot3\cdot...\cdot n$

反復解:

# iterative factorial
def fact_iter(n):
    result = 1
    # looping over numbers from 1 to n
    for num in range(1, n+1)
        result = num * result

    return result

$n = 4:$

result = 1

result = 1 * result(1) = 1
result = 2 * result(1) = 2
result = 3 * result(2) = 6
result = 4 * result(4) = 24

$4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24$

階乗 - 再帰法

$n!$ $=n\cdot(n-1)!$

def fact_rec(n):
    return n * fact_rec(n-1)

このコードの問題は？

fact_rec(4)

RecursionError

基本ケースが必要です！

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1$

停止条件 / 基本ケース: $1! = 1$

def fact_rec(n):
    if n == 1:
        return 1
    return n * fact_rec(n-1)

fact_rec(4)

まとめ

再帰関数には主に2要素があります:

自身のより小さい問題への再帰呼び出し
無限呼び出しを防ぐ基本ケース

例：決定木

決定木

決定木による分類

決定木の走査

x - 新しいサンプル $(x_1, x_2)$

# カテゴリを求める擬似アルゴリズム:

category = pred(node, x):

  # 分割があるか確認
  if node.hasSplitting:

    # どちらの子ノードに進むか判定
    if node.goToLeftChild(x):
      return pred(node.leftChild, x)   
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

決定木の走査

決定木による予測

x - 新しいサンプル $(x_1, x_2)$

# カテゴリを求める擬似アルゴリズム:

category = pred(node, x):

  # 分割があるか確認
  if node.hasSplitting:

    # どちらの子ノードに進むか判定
    if node.goToLeftChild(x):
      return pred(node.leftChild, x) 
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

  # カテゴリを返す
  return node.category

演習に進みましょう！

Pythonでコーディング面接問題を練習する