Recursion समझना

Python में Data Structures और Algorithms

Miriam Antona

Software engineer

परिभाषा

• फ़ंक्शन का खुद को कॉल करना
• लगभग हर जगह जहाँ हम loops इस्तेमाल करते हैं
  • loops की जगह recursion लगा सकते हैं
• पहली नज़र में बहुत जटिल लगने वाली समस्याएँ सुलझा सकते हैं

उदाहरण - factorial

$n!$

उदाहरण - factorial

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

120

उदाहरण - recursion से factorial

$n!= n$ · $(n-1)!$

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

• यह हमेशा चलता रहेगा!

उदाहरण - base case पहचानना

• एक शर्त जोड़ें
  • ताकि एल्गोरिदम अनंत समय तक न चले
• Factorial base case -> $n=1$

def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120

Recursion कैसे काम करता है

• कंप्यूटर फ़ंक्शनों पर नज़र रखने के लिए एक stack का उपयोग करता है
  • Call stack

Recursion कैसे काम करता है

• factorial(5) शुरू होता है
• factorial(5) खत्म होने से पहले -> factorial(4) शुरू
• factorial(4) खत्म होने से पहले -> factorial(3) शुरू

Recursion कैसे काम करता है

• factorial(5) शुरू होता है
• factorial(5) खत्म होने से पहले -> factorial(4) शुरू
• factorial(4) खत्म होने से पहले -> factorial(3) शुरू
• factorial(3) खत्म होने से पहले -> factorial(2) शुरू

Recursion कैसे काम करता है

• factorial(5) शुरू होता है
• factorial(5) खत्म होने से पहले -> factorial(4) शुरू
• factorial(4) खत्म होने से पहले -> factorial(3) शुरू
• factorial(3) खत्म होने से पहले -> factorial(2) शुरू
• factorial(2) खत्म होने से पहले -> factorial(1) शुरू

Recursion कैसे काम करता है

• factorial(5) शुरू होता है
• factorial(5) खत्म होने से पहले -> factorial(4) शुरू
• factorial(4) खत्म होने से पहले -> factorial(3) शुरू
• factorial(3) खत्म होने से पहले -> factorial(2) शुरू
• factorial(2) खत्म होने से पहले -> factorial(1) शुरू

Recursion कैसे काम करता है

• factorial(1) खत्म होता है
  • 1 लौटाता है
• factorial(2) खत्म होता है

Recursion कैसे काम करता है

• factorial(1) खत्म होता है
  • 1 लौटाता है
• factorial(2) खत्म होता है
  • 2 लौटाता है

Recursion कैसे काम करता है

• factorial(1) खत्म होता है
  • 1 लौटाता है
• factorial(2) खत्म होता है
  • 2 लौटाता है
• factorial(3) खत्म होता है
  • 6 लौटाता है

Recursion कैसे काम करता है

• factorial(1) खत्म होता है
  • 1 लौटाता है
• factorial(2) खत्म होता है
  • 2 लौटाता है
• factorial(3) खत्म होता है
  • 6 लौटाता है
• factorial(4) खत्म होता है
  • 24 लौटाता है

Recursion कैसे काम करता है

• factorial(1) खत्म होता है
  • 1 लौटाता है
• factorial(2) खत्म होता है
  • 2 लौटाता है
• factorial(3) खत्म होता है
  • 6 लौटाता है
• factorial(4) खत्म होता है
  • 24 लौटाता है
• factorial(5) खत्म होता है
  • 120 लौटाता है

Recursion कैसे काम करता है

• factorial(1) खत्म होता है
  • 1 लौटाता है
• factorial(2) खत्म होता है
  • 2 लौटाता है
• factorial(3) खत्म होता है
  • 6 लौटाता है
• factorial(4) खत्म होता है
  • 24 लौटाता है
• factorial(5) खत्म होता है
  • 120 लौटाता है

Dynamic programming

• Optimization तकनीक
• मुख्यतः recursion पर लागू
• recursive एल्गोरिदम की complexity घटा सकती है
• उपयोग:
  • कोई भी समस्या जिसे छोटे subproblems में बाँटा जा सके
  • subproblems में overlap हो
• subproblems के solutions सहेजे जाते हैं, दोबारा गणना से बचते हैं
  • Memoization

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

Python में Data Structures और Algorithms