الرئيسية › الدروس › العودية (Récursivité)

دروس هذا الفصل

1. دالة تنادي روحها
2. العودية على الـ chaînes
3. من التكرار للعودية

الدرس 21.1 : دالة تنادي روحها

11 دقيقة

الدالة récursive كي تنادي روحها. الفكرة: نحلّو مشكل كي نرجّعوه لـ نفس المشكل، أصغر. مثلا n! = n × (n − 1)!: باش نحسبو 5!، يكفي نعرفو نحسبو 4!.

• شرط توقّف (الحالة الأساسية): حالة بسيطة نحسبوها من غير نداء. للعاملي: 0! = 1.
• نداء عودي على مشكل أصغر، يقرّب للحالة الأساسية: n * fact(n - 1).

انتبه : من غير شرط توقّف، ولا كان النداء ما يقرّبش للحالة الأساسية، الدالة تنادي روحها بلا نهاية: Python يوقف بغلطة RecursionError.

نصيحة : كل نداء يستنّى نتيجة اللي بعدو. fact(3) تستنّى fact(2)، اللي تستنّى fact(1)، اللي تستنّى fact(0) = 1؛ وبعد الضربات تصير في الرجوع: 1، 1، 2، 6.

بـ Python

العاملي، مكتوب بطريقة عودية.

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)

n = int(input())
print(n, "! =", fact(n))

بـ algorithme

نفس الدالة في الـ algorithme: تنادي روحها في الـ Sinon.

DEF FN fact (n : Entier) : Entier
Début
  Si n = 0 Alors
    Retourner 1
  Sinon
    Retourner n * fact(n - 1)
  FinSi
Fin

Algorithme Factorielle
Début
  Lire(n)
  Ecrire(n, " ! = ", fact(n))
Fin

TDO
Objet | Type/Nature
n | Entier

الدرس 21.2 : العودية على الـ chaînes

11 دقيقة

الـ chaîne زادة نعالجوها بالعودية: نشوفو أول ولا آخر حرف، وبعد نناديو الدالة على باقي الـ chaîne. الحالة الأساسية ياسر مرّات هي الـ chaîne الفارغة ولا اللي فيها حرف واحد.

• Palindrome: كلمة تتقرا كيف كيف من الزوز جهات (radar). تكون palindrome كان أول حرف وآخر حرف كيف كيف و الوسط palindrome.
• في Python، ch[1:len(ch) - 1] هو الوسط؛ في الـ algorithme sous_chaine(ch, 1, long(ch) - 1).

نصيحة : نتيجة دالة عودية booléenne تنجم تتكتب بـ et: ch[0] == ch[-1] and palindrome(milieu).

بـ Python

اختبار الـ palindrome، بالعودية.

def palindrome(ch):
    if len(ch) <= 1:
        return True
    elif ch[0] != ch[len(ch) - 1]:
        return False
    else:
        return palindrome(ch[1:len(ch) - 1])

mot = input()
if palindrome(mot):
    print(mot, "est un palindrome")
else:
    print(mot, "n'est pas un palindrome")

بـ algorithme

sous_chaine(ch, 1, long(ch) - 1) تنحّي أول وآخر حرف.

DEF FN palindrome (ch : Chaîne) : Booléen
Début
  Si long(ch) ≤ 1 Alors
    Retourner Vrai
  Sinon Si ch[0] ≠ ch[long(ch) - 1] Alors
    Retourner Faux
  Sinon
    Retourner palindrome(sous_chaine(ch, 1, long(ch) - 1))
  FinSi
Fin

Algorithme Palindrome
Début
  Lire(mot)
  Si palindrome(mot) Alors
    Ecrire(mot, " est un palindrome")
  Sinon
    Ecrire(mot, " n'est pas un palindrome")
  FinSi
Fin

TDO
Objet | Type/Nature
mot | Chaîne

الدرس 21.3 : من التكرار للعودية

10 دقيقة

برشا algorithmes نكتبوهم بـ boucle عندهم شكل عودي طبيعي. خوارزمية إقليدس مثال: PGCD(a, b) = a كان b = 0، وإلا PGCD(a, b) = PGCD(b, a mod b).

• اللي يتبدّل في كل دورة يولّي الـ paramètres متاع النداء الجديد.
• شرط توقّف الـ boucle يولّي الحالة الأساسية.

نصيحة : الشكل العودي ياسر مرّات أقصر وقريب من التعريف الرياضي؛ والشكل التكراري يستعمل ذاكرة أقل.

بـ Python

القاسم المشترك الأكبر بإقليدس، بالعودية.

def pgcd(a, b):
    if b == 0:
        return a
    return pgcd(b, a % b)

a = int(input())
b = int(input())
print("PGCD =", pgcd(a, b))

بـ algorithme

النداء الجديد ياخذ b و a mod b.

DEF FN pgcd (a, b : Entier) : Entier
Début
  Si b = 0 Alors
    Retourner a
  Sinon
    Retourner pgcd(b, a mod b)
  FinSi
Fin

Algorithme Euclide
Début
  Lire(a)
  Lire(b)
  Ecrire("PGCD = ", pgcd(a, b))
Fin

TDO
Objet | Type/Nature
a, b | Entier

تدرّب مجانًا

كل درس فيه 3 تمارين مجانية مع تلميحات باش تطبّق الفصل هذا مع هنّيبوت.

← الفصل اللي قبل : التقريب والتحسين · الفصل اللي بعد : الخوارزميات التراجعية →

كل الفصول · شوف فروض 2 تكنولوجيا المصلّحة

الدروس كتبناها لـ Mission Carthage على أساس البرنامج الرسمي. الأستاذ متاعك يبقى المرجع.