Recursion क्या है?

Python में कोडिंग इंटरव्यू प्रश्नों का अभ्यास

Kirill Smirnov

Data Science Consultant, Altran

परिभाषा

Recursion में समस्या को खुद की ही शर्तों में परिभाषित किया जाता है
Recursion वह प्रक्रिया है जिसमें कोई फंक्शन खुद को सबरूटीन के तौर पर कॉल करता है

उदाहरण: Factorial $n!$

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

$n = 4$:

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

4! = 24

Factorial - Iterative तरीका

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

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

Iterative समाधान:

# 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$

Factorial - Recursive तरीका

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

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

उस कोड में दिक्कत क्या है?

fact_rec(4)

RecursionError

हमें base case ज़रूर परिभाषित करना होगा!

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

रुकने का मानदंड / base case: $1! = 1$

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

fact_rec(4)

समापन

Recursive फंक्शन के दो मुख्य हिस्से होते हैं:

अपने छोटे रूप पर recursive कॉल
अनंत कॉलिंग रोकने के लिए base case

उदाहरण - Decision Trees

डिसीजन ट्री

डिसीजन ट्री से क्लासिफिकेशन

Decision Tree को Traverse करना

डिसीजन ट्री को traverse करना

x - नया सैंपल $(x_1, x_2)$

# कैटेगरी निकालने का स्यूडो एल्गोरिदम:

category = pred(node, x):

  # देखें कि split है या नहीं  
  if node.hasSplitting:

    # तय करें किस child node पर जाएँ
    if node.goToLeftChild(x):
      return pred(node.leftChild, x)   
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

Decision Tree को Traverse करना

डिसीजन ट्री से prediction

x - नया सैंपल $(x_1, x_2)$

# कैटेगरी निकालने का स्यूडो एल्गोरिदम:

category = pred(node, x):

  # देखें कि split है या नहीं  
  if node.hasSplitting:

    # तय करें किस child node पर जाएँ
    if node.goToLeftChild(x):
      return pred(node.leftChild, x) 
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

  # कैटेगरी लौटाना
  return node.category

अभ्यास करते हैं!

Python में कोडिंग इंटरव्यू प्रश्नों का अभ्यास