PythonPython · Chapterبەش 8 · Lectureوانە 8.6

Recursionخۆبانگکردنەوە

Functions that call themselves: base case and recursive case, a countdown and factorial, fact(4) step by step, the call stack growing and shrinking, work done on the way back, RecursionError and the recursion limit, and when a loop is the better choice.

ئەو بانگی خۆیان دەکەنەوە: و ، ژماردنی پێچەوانە و ، ⁦fact(4)⁩ هەنگاو بە هەنگاو، گەورەبوون و بچووکبوونەوەی ، ئەو کارەی لە ڕێگای گەڕانەوەدا دەکرێت، RecursionError و سنووری . هەروەها کەی هەڵبژاردەیەکی باشترە.

14 min read14 خولەک خوێندنەوە · 15 stepsهەنگاو

What you will learnچی فێر دەبیت

Explain recursion and name the base case and the recursive case of a recursive function.
Write recursive functions such as countdown, factorial, sum and power.
Trace recursive calls on the call stack, including work done on the way back.
Recognise infinite recursion and RecursionError, and choose between recursion and a loop.

ڕوون بکەیتەوە و و خۆبانگکەر دیاری بکەیت.
خۆبانگکەری وەک ژماردنی پێچەوانە، ، کۆ و توان بنووسیت.
بەدوای بانگکردنە خۆبانگکەرەکاندا لەسەر بچیت، لەوانە ئەو کارەی لە ڕێگای گەڕانەوەدا دەکرێت.
بێکۆتا و RecursionError بناسیتەوە و لە نێوان و هەڵبژێریت.

A function that calls itselfکردارێک کە بانگی خۆی دەکاتەوە

You know that a function can call another function. It can also call itself. A function that calls itself is recursive, and the technique is called . The idea: to solve a big problem, solve a smaller copy of the same problem and use its answer — until the problem is so small that the answer is obvious.

دەزانیت دەتوانێت تر بانگ بکات. دەتوانێت بانگی خۆشی بکاتەوە. کە بانگی خۆی دەکاتەوە پێی دەوترێت خۆبانگکەر و ئەم ڕێگایە ناوی ـە. بیرۆکەکە: بۆ چارەسەرکردنی کێشەیەکی گەورە، وێنەیەکی بچووکتری هەمان کێشە چارەسەر بکە و وەڵامەکەی بەکار بهێنە — تا کێشەکە ئەوەندە بچووک دەبێت کە وەڵامەکەی ئاشکرایە.

Definitionپێناسە

When a function calls itself to solve a smaller copy of the same problem, until it reaches a case simple enough to answer directly.

کاتێکە کە بانگی خۆی دەکاتەوە بۆ چارەسەرکردنی وێنەیەکی بچووکتری هەمان کێشە، تا دەگاتە حاڵەتێک کە ئەوەندە سادەیە ڕاستەوخۆ وەڵام بدرێتەوە.

A function that calls itselfکردارێک کە بانگی خۆی دەکاتەوە

An everyday picture: the bakery queueوێنەیەکی ڕۆژانە: ڕیزی نانەواخانە

The bakery queueڕیزی نانەواخانە

You stand in a long queue at the bakery and want to know your place, but you can only see the person in front of you. You ask: "What is your place?" They do not know either, so they ask the person in front of them, and so on. The first person in the queue knows at once: "I am number 1" — that is the base case. Now the answers travel back: each person adds 1 to the answer they received and passes it back. You learn your place without anyone seeing the whole queue.

لە ڕیزێکی درێژی نانەواخانەدا وەستاویت و دەتەوێت بزانیت ژمارە چەندیت، بەڵام تەنها ئەو کەسە دەبینیت کە لە پێشتەوەیە. لێی دەپرسیت: «تۆ ژمارە چەندیت؟» ئەویش نازانێت، بۆیە لە کەسی پێش خۆی دەپرسێت و هەتا کۆتایی. یەکەم کەسی ڕیزەکە یەکسەر دەزانێت: «من ژمارە 1م» — ئەمە . ئێستا وەڵامەکان دەگەڕێنەوە: هەر کەسێک 1 بۆ ئەو وەڵامە زیاد دەکات کە وەریگرتووە و بۆ دواوەی دەنێرێتەوە. ژمارەی خۆت دەزانیت بەبێ ئەوەی کەس هەموو ڕیزەکە ببینێت.

Where the analogy stops workingسنووری ئەم نموونەیە

In Python every waiting question takes : a frame on the call stack. A queue of a few thousand people is too long — Python stops at about 1000 waiting calls with RecursionError. A loop that counts the people one by one has no such limit.

لە Pythonـدا هەر پرسیارێکی چاوەڕوان دەخوات: چوارچێوەیەک لەسەر . ڕیزێکی چەند هەزار کەسی زۆر درێژە — Python لە نزیکەی ⁦1000⁩ بانگکردنی چاوەڕواندا بە RecursionError دەوەستێت. کە یەک یەک خەڵکەکە بژمێرێت ئەم سنوورەی نییە.

First example: a countdownیەکەم نموونە: ژماردنی پێچەوانە

To count down from n, print n and then count down from n - 1 — the same job for a smaller number. When there is nothing left to count, say "Go!" and stop:

بۆ ژماردنی پێچەوانە لە nـەوە، n چاپ بکە و پاشان لە n - 1ـەوە بە پێچەوانە بژمێرە — هەمان کار بۆ ژمارەیەکی بچووکتر. کاتێک هیچ شتێک بۆ ژماردن نەما، بڵێ «⁦Go!⁩» و بوەستە:

countdown calls countdowncountdown بانگی countdown دەکاتcountdown.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def countdown(n):
    if n <= 0:              # base case: nothing left to count
        print("Go!")
    else:                   # recursive case
        print(n)
        countdown(n - 1)    # the same job for a smaller number


countdown(3)

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 2-3

The base case: n is 0 (or less). No more calls.

: n 0ـە (یان کەمتر). هیچ بانگکردنێکی تر نییە.

Lineدێڕی 4-6

The recursive case: print n, then call countdown with n - 1, one step closer to 0.

: n چاپ بکە، پاشان countdown بە n - 1 بانگ بکە، هەنگاوێک نزیکتر لە 0.

Follow it: countdown(3) prints 3 and calls countdown(2), which prints 2 and calls countdown(1), which prints 1 and calls countdown(0). That call is the base case: it prints Go! and does not call again. Then the four calls finish, the last one first.

بەدوایدا بچۆ: countdown(3) ژمارە 3 چاپ دەکات و countdown(2) بانگ دەکات، ئەویش 2 چاپ دەکات و countdown(1) بانگ دەکات، ئەویش 1 چاپ دەکات و countdown(0) بانگ دەکات. ئەو بانگکردنە : Go! چاپ دەکات و دیسان بانگ ناکاتەوە. پاشان چوار بانگکردنەکە تەواو دەبن، دوایینیان یەکەم.

Base case and recursive caseحاڵەتی بنچینە و حاڵەتی خۆبانگکردنەوە

Every recursive function has two parts:

هەموو خۆبانگکەر دوو بەشی هەیە:

A : a case simple enough to answer directly, without calling the function again. It stops the calls.
A : the function calls itself with a smaller value, and uses the answer.

: حاڵەتێک کە ئەوەندە سادەیە ڕاستەوخۆ وەڵام دەدرێتەوە، بەبێ بانگکردنەوەی . بانگکردنەکان دەوەستێنێت.
: بە نرخێکی بچووکتر بانگی خۆی دەکاتەوە و وەڵامەکە بەکار دەهێنێت.

Two rules make recursion work: (1) there must be a base case, and (2) every recursive call must move closer to it. Break either rule and the calls never end.

دوو یاسا وا دەکەن کار بکات: ⁦(1)⁩ دەبێت هەبێت و ⁦(2)⁩ هەموو بانگکردنێکی خۆبانگکەر دەبێت نزیکتر بێتەوە لێی. هەر کام لەم دوو یاسایە بشکێنیت، بانگکردنەکان کۆتاییان نایەت.

Factorial: a classic recursive functionفاکتۆریێل: کردارێکی خۆبانگکەری بەناوبانگ

The of a whole number n, written n!, is the product of all whole numbers from 1 to n. Notice that it contains a smaller factorial:

وەک n، کە بە n! دەنووسرێت، لێکدانی هەموو ژمارە تەواوەکانە لە 1 تا n. سەرنج بدە کە بچووکتری تێدایە:

n! = n \times (n-1) \times \cdots \times 2 \times 1 = n \times (n-1)!

That sentence is already a recursive function: the base case is n <= 1 (answer 1) and the recursive case is n * fact(n - 1):

ئەو ڕستەیە خۆی خۆبانگکەرە: n <= 1ـە (وەڵام ⁦1⁩) و n * fact(n - 1)ـە:

Factorial with recursionفاکتۆریێل بە خۆبانگکردنەوەfact.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def fact(n):
    if n <= 1:          # base case
        return 1
    return n * fact(n - 1)   # recursive case


print(fact(3), fact(5))

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 2-3

Base case. n <= 1 also covers fact(0), which is 1.

. n <= 1 هەروەها fact(0)ـیش دەگرێتەوە، کە 1ـە.

Lineدێڕی 4

Recursive case: a smaller copy of the same problem, then one multiplication.

: وێنەیەکی بچووکتری هەمان کێشە، پاشان یەک لێکدان.

Each call holds a smaller call inside it; the answers come back out: 1, then 2, then 6.هەر بانگکردنێک بانگکردنێکی بچووکتری لەناودایە؛ وەڵامەکان دێنەوە دەرەوە: 1، پاشان 2، پاشان 6.CêIT

You WILL Understand Recursion After Watching Thisb001 · Englishئینگلیزی · 47K viewsبینین · 2.8K likesلایک
A recursive factorial function traced call by call: the calls go down to the base case, then the answers are multiplied on the way back.
بە خۆبانگکەر، بانگکردن بە بانگکردن: بانگکردنەکان دادەبەزن تا ، پاشان لە گەڕانەوەدا وەڵامەکان لێکدەدرێن.
Whole video (3:46): factorial with recursion, with each call shown step by step.
هەموو ڤیدیۆکە ⁦(3:46)⁩: بە ، هەر بانگکردنێک هەنگاو بە هەنگاو پیشان دەدرێت.

Factorial: a classic recursive functionفاکتۆریێل: کردارێکی خۆبانگکەری بەناوبانگ

fact(4) step by step⁦fact(4)⁩ هەنگاو بە هەنگاو

Write out what each call returns. The calls go down to the base case; then the multiplications happen on the way back up:

بنووسە هەر بانگکردنێک چی دەگەڕێنێتەوە. بانگکردنەکان بەرەو خوار دەچن تا ؛ پاشان لێکدانەکان لە ڕێگای گەڕانەوەدا ڕوو دەدەن:

\begin{aligned} \text{fact}(4) &= 4 \times \text{fact}(3) \\ &= 4 \times 3 \times \text{fact}(2) \\ &= 4 \times 3 \times 2 \times \text{fact}(1) \\ &= 4 \times 3 \times 2 \times 1 = 24 \end{aligned}

You can make Python show this. This version prints a line when each call starts and when it returns, moved right by the depth of the call:

دەتوانیت وا لە Python بکەیت ئەمە پیشان بدات. ئەم وەشانە کاتێک هەر بانگکردنێک دەست پێدەکات و کاتێک دەگەڕێتەوە دێڕێک چاپ دەکات، بەپێی قووڵیی بانگکردنەکە بەرەو ڕاست دەڕوات:

Watching the callsسەیرکردنی بانگکردنەکانfact_trace.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def fact(n, depth=0):
    indent = "    " * depth           # deeper calls are printed further right
    print(f"{indent}fact({n}) starts")
    if n <= 1:
        print(f"{indent}fact({n}) is the base case: returns 1")
        return 1
    result = n * fact(n - 1, depth + 1)
    print(f"{indent}fact({n}) returns {n} * {result // n} = {result}")
    return result


print("Answer:", fact(4))

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 1

depth is only for printing: it counts how deep the call is.

depth تەنها بۆ چاپکردنە: دەژمێرێت بانگکردنەکە چەند قووڵە.

Lineدێڕی 7

The call goes deeper first; this line finishes only when fact(n - 1) has returned.

بانگکردنەکە سەرەتا قووڵتر دەبێتەوە؛ ئەم دێڕە تەنها کاتێک تەواو دەبێت کە fact(n - 1) گەڕابێتەوە.

The call stackستاکی بانگکردن

How can fact be running four times at once, each time with a different n? Every call gets its own frame: a small box with its own parameters and local variables (see Variable Scope). Python keeps the frames of all unfinished calls on the . A call puts a new frame on top; a return removes the top frame and hands its value to the frame below.

چۆن fact دەتوانێت لە یەک کاتدا چوار جار کار بکات، هەر جارە بە nـێکی جیاواز؟ هەر بانگکردنێک چوارچێوەی خۆی هەیە: سندوقێکی بچووک بە و خۆی (بڕوانە مەودای گۆڕاوەکان). Python چوارچێوەی هەموو بانگکردنە تەواونەبووەکان لەسەر هەڵدەگرێت. بانگکردنێک چوارچێوەیەکی نوێ دەخاتە سەرەوە؛ return چوارچێوەی سەرەوە لادەبات و نرخەکەی دەداتە چوارچێوەی خوارەوە.

Definitionپێناسە

The where a running program keeps one frame for every that has not finished yet, with its parameters and local variables. A call pushes a frame; a return pops it. Recursion that never stops fills it up (RecursionError in Python, StackOverflowError in Java).

ئەو کە لە کاتی کارکردندا بۆ هەر کە هێشتا تەواو نەبووە چوارچێوەیەکی تێدا هەڵدەگرێت، لەگەڵ و . هەر بانگکردنێک چوارچێوەیەک دەخاتە سەرەوە و هەر returnـێک لای دەبات. کە نەوەستێت پڕی دەکات (RecursionError لە Python و StackOverflowError لە Java).

Animation of the call stack for print(fact(4)). At the bottom is the main program. Frames pile up: fact(4) with n = 4 waiting for 4 * fact(3), then fact(3), then fact(2), then fact(1). fact(1) is the base case and returns 1. Then the frames come off one by one: fact(2) receives 1 and returns 2, fact(3) receives 2 and returns 6, fact(4) receives 6 and returns 24. Only the main program is left, and print shows 24. — The stack grows until the base case, then shrinks as each frame returns its value. تا گەورە دەبێت، پاشان کاتێک هەر چوارچێوەیەک نرخەکەی دەگەڕێنێتەوە بچووک دەبێتەوە.CêIT

This is also why recursion has a limit: every waiting call keeps a frame in memory until its answer arrives. The call stack is one of many stacks inside a computer: see Where computers use stacks.

هەر ئەمەش هۆی ئەوەیە کە سنووری هەیە: هەر بانگکردنێکی چاوەڕوان چوارچێوەیەک لە دەهێڵێتەوە تا وەڵامەکەی دەگات. یەکێکە لە چەندین لەناو : بڕوانە کۆمپیوتەر لە کوێ ستاک بەکار دەهێنێت.

The call stackستاکی بانگکردن

Work on the way back: counting upکار لە ڕێگای گەڕانەوەدا: ژماردن بەرەو سەرەوە

Code after the recursive call runs while the stack is shrinking, in the opposite order. Move the print below the call, and the countdown becomes a count-up:

ئەو کۆدەی دوای بانگکردنە خۆبانگکەرەکە دێت لە کاتی بچووکبوونەوەی جێبەجێ دەبێت، بە ڕیزبەندیی پێچەوانە. print ببە ژێر بانگکردنەکە، ژماردنی پێچەوانە دەبێتە ژماردن بەرەو سەرەوە:

print after the callprint دوای بانگکردنەکەcount_up.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def count_up(n):
    if n == 0:
        return            # base case: do nothing
    count_up(n - 1)       # first count up to n - 1 ...
    print(n)              # ... then print n, while the stack shrinks


count_up(3)

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 4

First all the calls go down to count_up(0) …

سەرەتا هەموو بانگکردنەکان دادەبەزن تا count_up(0) …

Lineدێڕی 5

… then each frame prints its own n as it finishes: 1, 2, 3.

… پاشان هەر چوارچێوەیەک لە کاتی تەواوبووندا nـی خۆی چاپ دەکات: 1، 2، 3.

When recursion never stopsکاتێک خۆبانگکردنەوە هەرگیز ناوەستێت

Without a base case, every call makes another call, and the stack grows until Python refuses to go deeper. Python stops the program with a RecursionError:

بەبێ ، هەر بانگکردنێک بانگکردنێکی تر دەکات و گەورە دەبێت تا Python ئامادە نابێت قووڵتر بڕوات. Python بە RecursionError دەوەستێنێت:

Recursion without a base caseخۆبانگکردنەوە بەبێ حاڵەتی بنچینەno_base.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def fact(n):
    return n * fact(n - 1)    # no base case: the calls never stop


print(fact(3))

The limit is the recursion limit, about 1000 nested calls by default. It protects your computer from a program that would otherwise use up its memory:

ئەم سنوورە سنووری ـە، کە بە شێوەی بنەڕەتی نزیکەی ⁦1000⁩ بانگکردنی ناو یەکە. کۆمپیوتەرەکەت لە دەپارێزێت کە ئەگینا هەموو بەکار دەهێنێت:

Asking for the limitپرسیار دەربارەی سنوورەکەlimit.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

import sys

print(sys.getrecursionlimit())

A base case that is never reached is just as bad. This countdown stops only at exactly 0, but 2.5 jumps from $0.5$ to $-0.5$ :

کە هەرگیز پێی نەگەیەنرێت هەر ئەوەندە خراپە. ئەم ژماردنە پێچەوانەیە تەنها ڕێک لە 0 دەوەستێت، بەڵام ⁦2.5⁩ لە $0.5$ ـەوە باز دەدات بۆ $-0.5$ :

The base case is skippedحاڵەتی بنچینەکە جێدەهێڵرێتnever_zero.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def countdown(n):
    if n == 0:
        print("Go!")
    else:
        print(n)
        countdown(n - 1)


countdown(2.5)     # 2.5, 1.5, 0.5, -0.5 ... never exactly 0

Recursion or a loop?خۆبانگکردنەوە یان خول؟

Anything a recursive function does can also be done with a loop. Here is factorial with a for loop, and the ready-made math.factorial() from the standard library:

هەر شتێک خۆبانگکەر بیکات بە دەکرێت. ئەمە بە ، لەگەڵ math.factorial()ـی ئامادە لە :

The same answers with a loopهەمان وەڵام بە خولfact_loop.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

import math


def fact_loop(n):
    result = 1
    for k in range(2, n + 1):
        result = result * k
    return result


print(fact_loop(4), fact_loop(5))
print(math.factorial(4), math.factorial(5))   # the standard library version

For very deep problems the loop wins: it needs no frame per step. The recursive fact(1200) needs 1200 nested calls — more than the limit — while the loop computes the same 3176-digit number without trouble:

بۆ کێشە زۆر قووڵەکان دەباتەوە: بۆ هەر هەنگاوێک پێویستی بە چوارچێوە نییە. fact(1200)ـی خۆبانگکەر پێویستی بە ⁦1200⁩ بانگکردنی ناو یەکە — زیاتر لە سنوورەکە — لە کاتێکدا هەمان ژمارەی ⁦3176⁩ ژمارەیی بەبێ کێشە دەژمێرێت:

A loop has no depth limitخول سنووری قووڵیی نییەdeep.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

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


def fact_loop(n):
    result = 1
    for k in range(2, n + 1):
        result = result * k
    return result


print(len(str(fact_loop(1200))), "digits")   # the loop has no depth limit
print(fact(1200))                            # 1200 nested calls are too many

Compareبەراورد	Recursion	Loop
Reads likeوەک … دەخوێنرێتەوە	the definition ( $n! = n \times (n-1)!$ )پێناسەکە ( $n! = n \times (n-1)!$ )	a list of stepsلیستێک لە هەنگاو
Memory	one frame per waiting callیەک چوارچێوە بۆ هەر بانگکردنێکی چاوەڕوان	a few variablesچەند
Depth limit in Pythonسنووری قووڵی لە Pythonـدا	about 1000 callsنزیکەی ⁦1000⁩ بانگکردن	noneنییە
Best forباشترە بۆ	problems that contain smaller copies of themselves: folders inside folders, trees, searchئەو کێشانەی وێنەی بچووکتری خۆیان تێدایە: لەناو ، دار، گەڕان	simple repetition: counting, totalsدووبارەبوونەوەی سادە: ژماردن، کۆکردنەوە

Recursion shines when a problem branches. In the AI course, a knowledge base is checked by trying every combination of true and false values recursively — see Another way: recursion — and depth-first search can be written recursively too (DFS and BFS).

کاتێک دەدرەوشێتەوە کە کێشەیەک لق دەکاتەوە. لە وانەی زیرەکیی دەستکرددا، بنکەیەکی زانیاری بە تاقیکردنەوەی هەموو تێکەڵەیەکی بە دەپشکنرێت — بڕوانە ڕێگایەکی تر: خۆبانگکردنەوە — هەروەها گەڕانی قووڵایی-یەکەم دەتوانرێت بە بنووسرێت (DFS و BFS).

Python: RECURSION ExplainedProgramming and Math Tutorials · Englishئینگلیزی · 320K viewsبینین · 6.2K likesلایک · Partبەشی 0:10–8:45 (ofلە 8:45)
5! written first with a loop and then recursively, and the pros and cons of recursion compared with a loop.
$5!$ سەرەتا بە و پاشان بە دەنووسرێت، لەگەڵ سوود و کەموکوڕییەکانی بەراورد بە .
From 0:10: find 5!, the iterative algorithm (0:59), the recursive one (2:05), recursion pros and cons (5:30).
لە ⁦0:10⁩ بەدواوە: دۆزینەوەی $5!$ ، چارەسەر بە ⁦(0:59)⁩، چارەسەری خۆبانگکەر ⁦(2:05)⁩ و سوود و کەموکوڕییەکانی ⁦(5:30)⁩.

Recursion or a loop?خۆبانگکردنەوە یان خول؟

Extra: when recursion repeats its own workزیادە: کاتێک خۆبانگکردنەوە کاری خۆی دووبارە دەکاتەوە

In the Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, 13 … each number is the sum of the two before it. The definition is recursive, with two base cases:

لە زنجیرەی فیبۆناچیدا، 0، 1، 1، 2، 3، 5، 8، ⁦13⁩ …، هەر ژمارەیەک کۆی ئەو دوو ژمارەیەیە کە پێش خۆی دێن. پێناسەکە خۆبانگکەرە و دوو هەیە:

\text{fib}(0) = 0, \quad \text{fib}(1) = 1, \quad \text{fib}(n) = \text{fib}(n-1) + \text{fib}(n-2)

Written straight from the definition, the function is short and correct, but every call makes two more calls. A second function counts them:

ئەگەر ڕاستەوخۆ لە پێناسەکەوە بنووسرێت، کورت و دروستە، بەڵام هەر بانگکردنێک دوو بانگکردنی تر دەکات. دووەم دەیانژمێرێت:

fib_recursive.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def fib(n):
    if n < 2:                          # base cases: fib(0) is 0, fib(1) is 1
        return n
    return fib(n - 1) + fib(n - 2)     # two recursive calls


def calls(n):
    """How many calls fib(n) makes, counting itself."""
    if n < 2:
        return 1
    return 1 + calls(n - 1) + calls(n - 2)


for n in [5, 10, 20, 30]:
    print(f"fib({n}) = {fib(n)} needs {calls(n)} calls")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 4

Two recursive calls: the number of calls grows about 1.6 times with every step of n.

دوو بانگکردنی خۆبانگکەر: ژمارەی بانگکردنەکان بە هەر هەنگاوێکی n نزیکەی ⁦1.6⁩ جار زیاد دەکات.

Lineدێڕی 7-11

calls(n) follows the same pattern: one call, plus the calls of the two smaller problems.

calls(n) هەمان شێوە دەگرێتە بەر: یەک بانگکردن، لەگەڵ بانگکردنەکانی دوو کێشە بچووکترەکە.

The same smaller problems are solved again and again.هەمان کێشە بچووکەکان دووبارە و دووبارە چارەسەر دەکرێنەوە.CêIT

Inside fib(30), fib(2) alone is worked out 514,229 times. The loop in The Fibonacci sequence needs only 30 steps for the same answer. Recursion fits when a problem splits into different smaller problems; when the same pieces come back again and again, use a loop.

لەناو fib(30)ـدا، تەنها fib(2) ⁦514,229⁩ جار دەژمێردرێت. زنجیرەی فیبۆناچی بۆ هەمان وەڵام تەنها ⁦30⁩ هەنگاوی پێویستە. گونجاوە کاتێک کێشەیەک دابەش دەبێت بۆ کێشەی بچووکتری جیاواز؛ کاتێک هەمان پارچەکان دووبارە و دووبارە دێنەوە، بەکار بهێنە.

Quick checkپشکنینی خێراWhy is the recursive fib(30) so slow?بۆچی fib(30)ـی خۆبانگکەر ئەوەندە هێواشە؟30 nested calls pass the recursion limit⁦30⁩ بانگکردنی ناو یەک لە سنووری خۆبانگکردنەوە تێدەپەڕنRecursion is always slower than a loopخۆبانگکردنەوە هەمیشە لە خول هێواشترەIt works out the same smaller values again and againهەمان نرخە بچووکترەکان دووبارە و دووبارە دەژمێرێتەوە

Recursion Simply Explained with Code Examples - Python for BeginnersPython Simplified · Englishئینگلیزی · 253K viewsبینین · 7.5K likesلایک · Partبەشی 2:43–8:25 (ofلە 9:07)
What recursion is, and a short Python function that calls itself until it reaches a simple case.
چییە، لەگەڵ نموونەی کورتی کە بانگی خۆی دەکاتەوە تا دەگاتە حاڵەتێکی سادە.
Watch 2:43–8:25: Fibonacci with recursion (3:49), with a loop (5:21), and which is faster (6:56).
لە ⁦2:43⁩ تا ⁦8:25⁩ سەیر بکە: فیبۆناچی بە ⁦(3:49)⁩، بە ⁦(5:21)⁩ و کامیان خێراترە ⁦(6:56)⁩.

Common mistakesهەڵە باوەکان

Mistakeهەڵە	What happensچی ڕوو دەدات	Fixچارەسەر
No base caseهیچ نییە	`RecursionError: maximum recursion depth exceeded`	Add a case that returns without callingحاڵەتێک زیاد بکە کە بەبێ بانگکردن بگەڕێتەوە
A base case that is never reached (`n == 0` with 2.5, or `n + 1` instead of `n - 1`) کە هەرگیز پێی ناگات (`n == 0` لەگەڵ ⁦2.5⁩، یان `n + 1` لەبری `n - 1`)	`RecursionError`	Use `<=`, and make every call move towards the base case`<=` بەکار بهێنە و وا بکە هەموو بانگکردنێک بەرەو بڕوات
Forgetting `return` before the recursive callلەبیرکردنی `return` پێش بانگکردنە خۆبانگکەرەکە	The result is lost; `None` comes back (often a `TypeError` later)ئەنجامەکە ون دەبێت؛ `None` دەگەڕێتەوە (زۆرجار دواتر `TypeError`)	`return n * fact(n - 1)`
Using recursion for very long simple repetitionبەکارهێنانی بۆ دووبارەبوونەوەی سادەی زۆر درێژ	`RecursionError` for big inputs`RecursionError` بۆ گەورە	Use a loop بەکار بهێنە
Raising the limit with `sys.setrecursionlimit()` to hide a bugبەرزکردنەوەی سنوورەکە بە `sys.setrecursionlimit()` بۆ شاردنەوەی	The real bug stays; Python may crash ڕاستەقینە دەمێنێتەوە؛ لەوانەیە Python تێک بشکێت	Fix the base case چاک بکە

The forgotten returnreturnـی لەبیرکراوmissing_return.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def fact(n):
    if n <= 1:
        return 1
    n * fact(n - 1)        # the result is computed ... and thrown away


print(fact(3))

Exercisesڕاهێنانەکان

ExerciseڕاهێنانSum from 1 to nکۆی 1 تا n

Write a recursive function sum_to(n) that returns $1 + 2 + \cdots + n$ . The base case is sum_to(0) = 0. Print sum_to(5) and sum_to(100).

خۆبانگکەر بە ناوی sum_to(n) بنووسە کە $1 + 2 + \cdots + n$ بگەڕێنێتەوە. sum_to(0) = 0ـە. sum_to(5) و sum_to(100) چاپ بکە.

Hintئاماژە

sum_to(n) is n + sum_to(n - 1): the sum up to $n$ is $n$ plus the sum up to $n - 1$ .

sum_to(n) یەکسانە بە n + sum_to(n - 1): کۆی تا $n$ بریتییە لە $n$ لەگەڵ کۆی تا $n - 1$ .

Show answerوەڵامەکە پیشان بدە

sum_to.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def sum_to(n):
    if n == 0:                 # base case
        return 0
    return n + sum_to(n - 1)   # recursive case


print(sum_to(5))
print(sum_to(100))

ExerciseڕاهێنانPowerتوان

Write power(base, exponent) recursively for whole exponents ( $e \ge 0$ ), using $b^0 = 1$ and $b^e = b \times b^{e-1}$ . Print power(2, 10), power(5, 3) and power(7, 0).

power(base, exponent) بە بنووسە بۆ تەواو ( $e \ge 0$ )، بە بەکارهێنانی $b^0 = 1$ و $b^e = b \times b^{e-1}$ . power(2, 10)، power(5, 3) و power(7, 0) چاپ بکە.

Show answerوەڵامەکە پیشان بدە

power.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def power(base, exponent):
    if exponent == 0:                       # base case: anything ** 0 is 1
        return 1
    return base * power(base, exponent - 1)


print(power(2, 10))
print(power(5, 3))
print(power(7, 0))

ExerciseڕاهێنانReverse a stringپێچەوانەکردنەوەی زنجیرەنووسەیەک

Write reverse(text) recursively: a text of length 0 or 1 is its own reverse; otherwise reverse everything after the first letter and put the first letter at the end. Print reverse("Newroz") and reverse("tea").

reverse(text) بە بنووسە: دەقێک بە درێژیی 0 یان 1 پێچەوانەکەی خۆیەتی؛ ئەگینا هەموو ئەوەی دوای پیتی یەکەم دێت پێچەوانە بکەرەوە و پیتی یەکەم بخە کۆتایی. reverse("Newroz") و reverse("tea") چاپ بکە.

Hintئاماژە

text[1:] is everything after the first character; text[0] is the first character. See Slicing.

text[1:] هەموو ئەوەیە کە دوای یەکەم پیت دێت؛ text[0] یەکەم پیتە. بڕوانە لەتکردن.

Show answerوەڵامەکە پیشان بدە

reverse.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def reverse(text):
    if len(text) <= 1:                  # base case: "" or one letter
        return text
    return reverse(text[1:]) + text[0]  # reverse the rest, then add the first letter


print(reverse("Newroz"))
print(reverse("tea"))

ExerciseڕاهێنانCount the digitsتاکژمارەکان بژمێرە

Write count_digits(n) for a whole number $n \ge 0$ : a number below 10 has 1 digit; otherwise it has one more digit than n // 10. Print count_digits(7) and count_digits(2026).

count_digits(n) بنووسە بۆ $n \ge 0$ : ژمارەیەک کە لە ⁦10⁩ کەمترە 1 هەیە؛ ئەگینا زیاتری هەیە لە n // 10. count_digits(7) و count_digits(2026) چاپ بکە.

Show answerوەڵامەکە پیشان بدە

count_digits.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def count_digits(n):
    if n < 10:                       # base case: one digit
        return 1
    return 1 + count_digits(n // 10) # drop the last digit


print(count_digits(7))
print(count_digits(2026))

ExerciseڕاهێنانTrace itبەدوایدا بچۆ

Without running it: what does count_up(2) from this lesson print, and in which order are the frames removed from the stack?

بەبێ جێبەجێکردن: count_up(2)ـی ئەم وانەیە چی چاپ دەکات و چوارچێوەکان بە چ ڕیزبەندییەک لە لادەبرێن؟

Show answerوەڵامەکە پیشان بدە

Outputدەرئەنجام

1
2

The frames are pushed in the order count_up(2), count_up(1), count_up(0) and removed in the opposite order: count_up(0) (prints nothing), then count_up(1) prints 1, then count_up(2) prints 2.

چوارچێوەکان بەم ڕیزبەندییە دەخرێنە سەر : count_up(2)، count_up(1)، count_up(0) و بە پێچەوانەوە لادەبرێن: count_up(0) (هیچ چاپ ناکات)، پاشان count_up(1) ژمارە 1 چاپ دەکات، پاشان count_up(2) ژمارە 2 چاپ دەکات.

Summaryپوختە

A recursive function calls itself to solve a smaller copy of the same problem.
It needs a base case (answered directly) and a recursive case that moves closer to the base case.
$n! = n \times (n-1)!$ with $1! = 1$ becomes return n * fact(n - 1) with the base case n <= 1.
Each call has its own frame on the call stack; the stack grows to the base case and shrinks as the answers return. Code after the recursive call runs on the way back.
No base case, or one never reached → RecursionError after about 1000 calls (sys.getrecursionlimit()).
A function with two recursive calls can repeat the same work many times (Fibonacci): then a loop is far faster.
Loops are better for long simple repetition; recursion is natural for problems that branch into smaller copies.

خۆبانگکەر بانگی خۆی دەکاتەوە بۆ چارەسەرکردنی وێنەیەکی بچووکتری هەمان کێشە.
پێویستی بە (کە ڕاستەوخۆ وەڵام دەدرێتەوە) و هەیە کە لە نزیکتر دەبێتەوە.
$n! = n \times (n-1)!$ لەگەڵ $1! = 1$ دەبێتە return n * fact(n - 1) لەگەڵ n <= 1.
هەر بانگکردنێک چوارچێوەی خۆی لەسەر هەیە؛ تا گەورە دەبێت و کاتێک وەڵامەکان دەگەڕێنەوە بچووک دەبێتەوە. ئەو کۆدەی دوای بانگکردنە خۆبانگکەرەکە دێت لە ڕێگای گەڕانەوەدا جێبەجێ دەبێت.
هیچ نەبێت، یان پێی نەگات ← RecursionError دوای نزیکەی ⁦1000⁩ بانگکردن (sys.getrecursionlimit()).
بە دوو بانگکردنی خۆبانگکەر دەتوانێت هەمان کار زۆر جار دووبارە بکاتەوە (فیبۆناچی): ئەو کاتە زۆر خێراترە.
بۆ دووبارەبوونەوەی سادەی درێژ باشترن؛ بۆ ئەو کێشانەی لق دەکەنەوە بۆ وێنەی بچووکتر سروشتییە.

Review questionsپرسیارەکانی پێداچوونەوە

What are the two parts of a recursive function?دوو بەشی کردارێکی خۆبانگکەر چین؟

A base case that returns without calling again, and a recursive case that calls the function with a smaller problem.

کە بەبێ بانگکردنەوە دەگەڕێتەوە و کە بە کێشەیەکی بچووکتر بانگ دەکاتەوە.

What is on the call stack while fact(1) runs inside fact(3)?لە کاتێکدا fact(1) لەناو fact(3)ـدا کار دەکات، چی لەسەر ستاکی بانگکردنە؟

The main program's frame and the frames of fact(3), fact(2) and fact(1), each with its own n.

چوارچێوەی سەرەکی و چوارچێوەکانی fact(3)، fact(2) و fact(1)، هەر یەکەیان بە nـی خۆی.

When should you prefer a loop?کەی دەبێت خول هەڵبژێریت؟

When the repetition is simple and may be long — thousands of steps would pass the recursion limit.

کاتێک دووبارەبوونەوەکە سادەیە و لەوانەیە درێژ بێت — هەزاران هەنگاو لە سنووری تێدەپەڕن.

This ends the Functions chapter. The next chapter is about lists: keeping many values under one name.

ئەمە کۆتایی بەشی . بەشی داهاتوو دەربارەی : هەڵگرتنی زۆر نرخ لە ژێر یەک ناودا.

Videoڤیدیۆ

Watch a videoسەیری ڤیدیۆیەک بکە

A video that viewers liked a lot and praised in their comments, chosen for this lesson.ڤیدیۆیەک کە بینەران زۆریان پێ خۆش بووە و لە کۆمێنتەکانیاندا ستایشیان کردووە، بۆ ئەم وانەیە هەڵبژێردراوە.

Learn RECURSION in 5 minutes! 😵Bro Code · Englishئینگلیزی · 372K viewsبینین · 10K likesلایک
A function that calls itself: one walk written with a loop and with recursion, the base case that stops it, and why loops are faster.
کە بانگی خۆی دەکاتەوە: هەمان ڕۆیشتن جارێک بە و جارێک بە دەنووسرێت، کە ڕایدەگرێت و بۆچی خێراترن.
Whole video (5:59): iterative vs recursive walk(); the print after the recursive call shows work done on the way back.
هەموو ڤیدیۆکە ⁦(5:59)⁩: `walk()` بە بەرامبەر بە ؛ ئەو `print`ـەی دوای بانگکردنەوەکە دێت ئەو کارە پیشان دەدات کە لە ڕێگەی گەڕانەوەدا دەکرێت.

Lesson complete!وانەکە تەواو بوو!

Well done. Review the key terms, then go on to the next lesson.دەستخۆش. سەیرێکی زاراوە سەرەکییەکان بکەرەوە، پاشان بڕۆ بۆ وانەی داهاتوو.

Key termsزاراوە سەرەکییەکان

Next lessonوانەی داهاتوو

Lists: Creating and Indexingلیستەکان: دروستکردن و ئیندێکسەکان

Related lecturesوانە پەیوەندیدارەکان

References and further readingسەرچاوەکان و خوێندنەوەی زیاتر

This lecture is a first edition. The Kurdish text and terminology are waiting for review by Kurdish IT teachers.ئەم وانەیە چاپی یەکەمە. دەقە کوردییەکە و زاراوەکانی چاوەڕێی پێداچوونەوەی مامۆستایانی کوردی بواری IT ن.