JavaJava · Chapterبەش 8 · Lectureوانە 8.3

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

Methods that call themselves: adding 1 to 10, the base case (halting condition) and the recursive case, a range sum, countdown and count-up, factorial and its overflow, the call stack traced for factorial(4), StackOverflowError from a missing or unreachable base case, Fibonacci with its call tree and why it is slow (counted calls), and when to use a loop instead.

ئەو بانگی خۆیان دەکەنەوە: کۆکردنەوەی 1 تا ⁦10⁩، (مەرجی وەستان) و ، کۆی ژمارەکانی نێوان دوو ژمارە، ژماردنی پێچەوانە و ژماردن بەرەو سەرەوە، و ، بۆ ⁦factorial(4)⁩، StackOverflowError کاتێک نییە یان بانگکردنەکان ناگەنە ئەو، فیبۆناچی لەگەڵ داری بانگکردنەکانی و بۆچی خاوە (بانگکردنی ژمێردراو) و کەی باشترە.

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

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

Write recursive methods with a base case and a recursive case that moves closer to it.
Trace recursion on the call stack and explain StackOverflowError.
Count the calls of naive Fibonacci and explain why it is slow.
Choose between recursion and a loop, and rewrite one as the other.

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

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

A method can call other methods — and it can call itself. That is . 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. The same idea in Python: Recursion.

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

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.

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

Nesting dolls: every problem holds a smaller copy of itselfبووکەڵەی لە ناو یەک: هەر کێشەیەک وێنەیەکی بچووکتری خۆی تێدایەCêIT

Like Russian nesting dolls: open one and there is a smaller one inside, until the smallest, which does not open. In recursion the smallest problem, answered without another call, is the .

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

Adding 1 to 10 by recursionکۆکردنەوەی 1 تا ⁦10⁩ بە خۆبانگکردنەوە

The sum of 1 to 10 is 10 plus the sum of 1 to 9 — a smaller copy of the same job. Keep going down until the sum of nothing, which is 0:

کۆی 1 تا ⁦10⁩ دەکاتە ⁦10⁩ لەگەڵ کۆی 1 تا 9 — وێنەیەکی بچووکتری هەمان کار. بەرەو خوارەوە بڕۆ تا کۆی هیچ، کە 0ـە:

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

public class RecursiveSum {
    public static void main(String[] args) {
        System.out.println(sum(10));
        System.out.println(sum(5));
    }

    static int sum(int k) {
        if (k <= 0) {
            return 0;
        }
        return k + sum(k - 1);
    }
}

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

Lineدێڕی 8-10

The base case: sum(0) (or k when it is negative) is 0, with no new call.

: sum(0) (یان k ئەگەر بێت) دەکاتە 0، بەبێ بانگکردنی نوێ.

Lineدێڕی 11

The recursive case: k plus the sum of the numbers below it.

: k لەگەڵ کۆی ژمارەکانی خوارتر لە ئەو.

\begin{aligned} \text{sum}(10) &= 10 + \text{sum}(9) = 10 + 9 + \text{sum}(8) = \cdots \\ &= 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + \text{sum}(0) = 55 \end{aligned}

sum(4): the calls go down, the answers come back up⁦sum(4)⁩: بانگکردنەکان دەچنە خوارەوە، وەڵامەکان دەگەڕێنەوە سەرەوەCêIT

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

Every recursive method has two parts: a (also called the halting condition), answered directly, and a , where the method calls itself with a smaller problem. Two rules make it work: (1) a base case must exist, and (2) every recursive call must move closer to it. Break either rule and the calls never end.

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

Definitionپێناسە

In , the simple case that is answered directly, without calling the function again, such as 'fact(0) is 1'. It stops the calls; without it they never end and Python stops with RecursionError.

لە ، ئەو حاڵەتە سادەیەیە کە ڕاستەوخۆ وەڵام دەدرێتەوە بەبێ بانگکردنەوەی ، وەک «⁦fact(0)⁩ دەکاتە 1». بانگکردنەکان دەوەستێنێت؛ بەبێ ئەو کۆتاییان نایەت و Python بە RecursionError دەوەستێت.

Every call is one step closer to the floorهەر بانگکردنێک یەک پلە نزیکتر دەبێتەوە لە زەویCêIT

Make the base case catch everything it should: if (k <= 0) also stops a start below 0, while if (k == 0) would let sum(-1) run away for ever.

وا بکە هەموو ئەوەی پێویستە بیگرێت: if (k <= 0) ئەگەر k لە سەرەتاوە بێت، ئەویش دەوەستێنێت، لە کاتێکدا if (k == 0) ڕێگە دەدات sum(-1) بۆ هەمیشە بڕوات.

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

A halting condition with two parametersمەرجی وەستان بە دوو پارامیتەر

The numbers from from to to can be added the same way: take from, then add the rest, which starts one higher. The halting condition is an empty range, when from has passed to:

ژمارەکانی نێوان from و to بە هەمان شێوە کۆ دەکرێنەوە: from وەربگرە، پاشان باقییەکەی بخەرە سەر، کە یەکێک بەرزتر دەست پێ دەکات. مەرجی وەستان کاتێکە کە ژمارەکان تەواو دەبن، واتە from لە to تێپەڕیوە:

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

public class RangeSum {
    public static void main(String[] args) {
        System.out.println(sumRange(5, 10));
        System.out.println(sumRange(1, 100));
        System.out.println(sumRange(8, 3));
    }

    static int sumRange(int from, int to) {
        if (from > to) {
            return 0;
        }
        return from + sumRange(from + 1, to);
    }
}

from moves up until it passes tofrom بەرەو سەرەوە دەڕوات تا لە to تێدەپەڕێتCêIT

Countdown, and work on the way backژماردنی پێچەوانە و کار لە ڕێگای گەڕانەوەدا

A recursive method does not have to return a value. countdown prints n and then counts down from n - 1; at 0 it says Go! and stops:

پێویست ناکات خۆبانگکەر بگەڕێنێتەوە. countdown n چاپ دەکات و پاشان لە n - 1ـەوە ژماردنی پێچەوانە دەکات؛ لە 0ـدا Go! دەڵێت و دەوەستێت:

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

public class Countdown {
    public static void main(String[] args) {
        countdown(5);
    }

    static void countdown(int n) {
        if (n <= 0) {
            System.out.println("Go!");
            return;
        }
        System.out.println(n);
        countdown(n - 1);
    }
}

Now move the println below the call. The calls still go down to 0 first, and each number is printed while the calls return, in the opposite order:

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

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

public class CountUp {
    public static void main(String[] args) {
        countUp(5);
    }

    static void countUp(int n) {
        if (n <= 0) {
            return;
        }
        countUp(n - 1);
        System.out.println(n);
    }
}

Before the call: on the way down; after the call: on the way backپێش بانگکردن: لە ڕێگای دابەزیندا؛ دوای بانگکردن: لە ڕێگای گەڕانەوەداCêIT

Factorialفاکتۆریێل

The of n, written $n!$ , multiplies all whole numbers from 1 to n, and $0! = 1$ . It contains a smaller factorial, so it is recursive by nature:

ی n، کە بە $n!$ دەنووسرێت، هەموو لە 1 تا n لێک دەدات و $0! = 1$ . بچووکتری تێدایە، بۆیە لە سروشتیدا خۆبانگکەرە:

n! = n \times (n-1)!, \qquad 1! = 0! = 1 \qquad\Rightarrow\qquad 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120

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

public class Factorial {
    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5));
        System.out.println("0! = " + factorial(0));
        System.out.println("10! = " + factorial(10));
        System.out.println("20! = " + factorial(20));
    }

    static long factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }
}

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

Lineدێڕی 9

long, not int: factorials grow very fast.

long، نەک int: زۆر خێرا گەورە دەبن.

Lineدێڕی 10-12

Base case: 0! and 1! are 1.

: ⁦0!⁩ و ⁦1!⁩ دەکەنە 1.

Lineدێڕی 13

Recursive case: n times the factorial of n - 1.

: n جارانی ⁦n - 1⁩.

Factorialفاکتۆریێل

When the result is too bigکاتێک ئەنجامەکە زۆر گەورەیە

$13!$ is 6,227,020,800, more than the largest int (2,147,483,647). Java does not stop; the number wraps round to a wrong value without any message (Overflow). long reaches $20!$ , but $21!$ wraps too:

$13!$ دەکاتە ⁦6,227,020,800⁩، کە لە گەورەترین int ⁦(2,147,483,647)⁩ زیاترە. Java ناوەستێت؛ ژمارەکە دەسوڕێتەوە بۆ هەڵە بەبێ هیچ پەیامێک (سەرڕێژبوون). long تا $20!$ دەگات، بەڵام $21!$ دەسوڕێتەوە:

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

public class FactorialOverflow {
    public static void main(String[] args) {
        System.out.println("12! as int  = " + factorialInt(12));
        System.out.println("13! as int  = " + factorialInt(13));
        System.out.println("13! as long = " + factorial(13));
        System.out.println("21! as long = " + factorial(21));
    }

    static int factorialInt(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorialInt(n - 1);
    }

    static long factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }
}

int holds up to 12!, long up to 20!int تا ⁦12!⁩ و long تا ⁦20!⁩ هەڵدەگرنCêIT

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

How can factorial run 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. Java keeps the frames of all unfinished calls on the . A call pushes a new frame on top; a return pops the top frame and hands its value to the frame below (Java Virtual Machine Specification §2.5.2, §2.6). Other languages use a call stack in the same way: Memory While a Program Runs.

چۆن factorial دەتوانێت لە یەک کاتدا چوار جار کار بکات، هەر جارێک بە nـێکی جیاواز؟ هەر بانگکردنێک چوارچێوەی خۆی وەردەگرێت: سندووقێکی بچووک بە و خۆی. Java چوارچێوەی هەموو بانگکردنە تەواونەبووەکان لەسەر هەڵدەگرێت. بانگکردنێک چوارچێوەیەکی نوێ دەخاتە سەرەوە ⁦(push)⁩؛ return چوارچێوەی سەرەوە لادەبات ⁦(pop)⁩ و دەداتە چوارچێوەی خوارەوە (Java Virtual Machine Specification §⁦2.5.2⁩، §⁦2.6⁩). زمانەکانی تریش بە هەمان شێوە بەکار دەهێنن: بیرگە لە کاتی کارکردنی بەرنامەدا.

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).

An animation of the call stack for factorial(4), next to the code. main is at the bottom. A frame factorial(4) with n = 4 is pushed, then factorial(3), factorial(2) and factorial(1), each lower frame waiting for the one above. factorial(1) is the base case and returns 1. Then the frames are popped one by one: factorial(2) gets 1 and returns 2, factorial(3) returns 6, factorial(4) returns 24, and main prints 24. — factorial(4): frames pushed down to the base case, then popped with 1, 2, 6, 24⁦factorial(4)⁩: چوارچێوەکان تا دەخرێنە سەر یەک، پاشان بە 1، 2، 6، ⁦24⁩ لادەبرێنCêIT

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

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

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

public class FactorialTrace {
    public static void main(String[] args) {
        long answer = factorial(4, "");
        System.out.println("Answer: " + answer);
    }

    static long factorial(int n, String indent) {
        System.out.println(indent + "factorial(" + n + ") starts");
        if (n <= 1) {
            System.out.println(indent + "factorial(" + n + ") returns 1 (base case)");
            return 1;
        }
        long smaller = factorial(n - 1, indent + "    ");
        long result = n * smaller;
        System.out.println(indent + "factorial(" + n + ") returns " + n + " * " + smaller + " = " + result);
        return result;
    }
}

No base case: StackOverflowErrorبێ حاڵەتی بنچینە: StackOverflowError

Without a base case, every call makes another call, and the frames pile up until the stack has no room left. The JVM then stops the program with a , the error StackOverflowError. The main thread, which runs main, has a stack of fixed size: by default 1 MB on 64-bit Linux and macOS (changed with the -Xss option of the java command):

بەبێ ، هەموو بانگکردنێک بانگکردنێکی تر دەکات و چوارچێوەکان لەسەر یەک کەڵەکە دەبن تا هیچ شوێنی نامێنێت. ئەوکات JVM بە دەوەستێنێت، هەڵەی StackOverflowError. ، کە main جێبەجێ دەکات، قەبارە جێگیری هەیە: بە شێوەی بنەڕەتی لەسەر Linux و macOSـی ⁦64-bit⁩ یەک مێگابایتە (بە هەڵبژاردەی -Xssـی java دەگۆڕدرێت):

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

public class NoBase {
    public static void main(String[] args) {
        System.out.println(sum(10));
    }

    static int sum(int k) {
        return k + sum(k - 1);
    }
}

With no base case the frames pile up until the stack is fullبێ چوارچێوەکان کەڵەکە دەبن تا پڕ دەبێتCêIT

Read it like any stack trace (Reading a stack trace): every at line is one waiting call, all on line 7. Java printed 1,024 of them and left out the rest — the real stack was deeper. StackOverflowError is an Error, not an ordinary exception: do not try to catch it (Exceptions); fix the base case.

وەک هەر بیخوێنەوە (خوێندنەوەی ڕێچکەیەکی هەڵە): هەر دێڕێکی at یەک بانگکردنی چاوەڕوانە، هەموویان لە دێڕی ⁦7. Java 1,024⁩ـیانی چاپ کرد و باقییەکەی نەنووسی — قووڵتر بوو. StackOverflowError Errorـە، نەک ئاسایی: هەوڵی گرتنی مەدە (هەڵاوێردەکان)؛ چاک بکە.

No base case: StackOverflowErrorبێ حاڵەتی بنچینە: StackOverflowError

A base case that is never reachedحاڵەتێکی بنچینە کە هەرگیز ناگەیەنرێت

A base case that the calls jump over is as bad as none. countdownByTwo stops only at exactly 0, but from 5 it goes 5, 3, 1, $-1$ …:

کە بانگکردنەکان بەسەریدا باز بدەن وەک ئەوە وایە هەر نەبێت. countdownByTwo تەنیا لە ڕێک 0ـدا دەوەستێت، بەڵام لە 5ـەوە بەم شێوەیە دەڕوات: 5، 3، 1، $-1$ …:

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

public class NeverReached {
    public static void main(String[] args) {
        countdownByTwo(5);
    }

    static void countdownByTwo(int n) {
        if (n == 0) {
            System.out.println("Go!");
            return;
        }
        System.out.println(n);
        countdownByTwo(n - 2);
    }
}

Jumping by 2 from an odd number misses 0باز بە 2 لە ژمارەیەکی تاکەوە 0 لەدەست دەداتCêIT

In one run on our computer it printed 47,757 numbers before the stack was full (the count changes a little from run to run) — and the last call happened to be inside println, so the trace starts in Java's own classes. Use if (n <= 0).

لە جێبەجێکردنێکدا لەسەر پێش پڕبوونی ⁦47,757⁩ ژمارەی چاپ کرد (ژمارەکە لە جێبەجێکردنێکەوە بۆ یەکێکی تر کەمێک دەگۆڕێت) — و دوا بانگکردن بە ڕێکەوت لە ناو printlnـدا بوو، بۆیە لە خودی Javaـەوە دەست پێ دەکات. if (n <= 0) بەکار بهێنە.

Fibonacci: two recursive callsفیبۆناچی: دوو بانگکردنی خۆبانگکەرانە

In the Fibonacci numbers 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, \qquad \text{fib}(1) = 1, \qquad \text{fib}(n) = \text{fib}(n-1) + \text{fib}(n-2)

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

public class Fibonacci {
    public static void main(String[] args) {
        for (int n = 0; n <= 10; n++) {
            System.out.print(fib(n) + " ");
        }
        System.out.println();
    }

    static int fib(int n) {
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
}

fib(5) makes 15 calls, and works some of them out more than once⁦fib(5)⁩ پازدە بانگکردن دەکات و هەندێکیان زیاتر لە جارێک دەدۆزێتەوەCêIT

Fibonacci: two recursive callsفیبۆناچی: دوو بانگکردنی خۆبانگکەرانە

Why naive Fibonacci is slowبۆچی فیبۆناچیی ساکار خاوە

Every call makes two more calls, so the work explodes. A class variable calls counts them (the times are from our computer and will differ on yours):

هەر بانگکردنێک دوو بانگکردنی تر دەکات، بۆیە کارەکە دەتەقێتەوە. ، calls، دەیانژمێرێت (کاتەکان هی و لەسەر هی تۆ جیاواز دەبن):

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

public class FibCalls {
    static long calls = 0;

    public static void main(String[] args) {
        test(5);
        test(10);
        test(20);
        test(30);
        test(40);
    }

    static void test(int n) {
        calls = 0;
        long start = System.nanoTime();
        long answer = fib(n);
        long ms = (System.nanoTime() - start) / 1_000_000;
        System.out.println("fib(" + n + ") = " + answer + "  calls: " + calls + "  time: " + ms + " ms");
    }

    static long fib(int n) {
        calls++;
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
}

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

Lineدێڕی 14-16

System.nanoTime() reads a clock in nanoseconds (billionths of a second); the difference divided by 1,000,000 is the time in milliseconds. In 1_000_000 the underscores only make the number easier to read.

System.nanoTime() کاتژمێرێک بە نانۆچرکە دەخوێنێتەوە (یەک لە ملیاری چرکەیەک)؛ جیاوازییەکە دابەش بە ⁦1,000,000⁩ کاتەکە بە میلیچرکە دەدات. لە 1_000_000ـدا هێڵە ژێرینەکان تەنیا خوێندنەوەی ژمارەکە ئاسانتر دەکەن.

Every +10 in n multiplies the calls by about 123هەر جارێک n بە ⁦10⁩ زیاد بکرێت، بانگکردنەکان نزیکەی ⁦123⁩ هێندە دەبنCêIT

The count follows a pattern: fib(n) makes $2 \times \text{fib}(n+1) - 1$ calls, so it grows like the Fibonacci numbers themselves, about 1.6 times for every step of n. Inside fib(40), fib(2) alone is worked out 63,245,986 times. A loop computes the same number in $n - 1$ additions:

ژمارەکە نەخشێکی هەیە: ⁦fib(n)⁩ $2 \times \text{fib}(n+1) - 1$ بانگکردن دەکات، بۆیە وەک خودی ژمارەکانی فیبۆناچی گەورە دەبێت، نزیکەی ⁦1.6⁩ هێندە بۆ هەر هەنگاوێکی n. لە ناو ⁦fib(40)⁩ـدا تەنیا ⁦fib(2) 63,245,986⁩ جار دەدۆزرێتەوە. هەمان ژمارە بە $n - 1$ دەدۆزێتەوە:

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

public class FibLoop {
    public static void main(String[] args) {
        System.out.println("fib(10) = " + fibLoop(10));
        System.out.println("fib(40) = " + fibLoop(40));
        System.out.println("fib(90) = " + fibLoop(90));
    }

    static long fibLoop(int n) {
        long previous = 0;
        long current = 1;
        if (n == 0) {
            return 0;
        }
        for (int i = 2; i <= n; i++) {
            long next = previous + current;
            previous = current;
            current = next;
        }
        return current;
    }
}

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

Anything a recursive method does can also be done with a loop, and the answers are the same:

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

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

public class LoopVersions {
    public static void main(String[] args) {
        System.out.println(factorial(5) + " " + factorialLoop(5));
        System.out.println(factorial(20) + " " + factorialLoop(20));
    }

    static long factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    static long factorialLoop(int n) {
        long result = 1;
        for (int i = 2; i <= n; i++) {
            result = result * i;
        }
        return result;
    }
}

The difference is the stack. A loop reuses one frame; recursion needs one frame for every waiting call. 100,000 nested calls do not fit in the default stack, while the loop has no limit. More stack room (-Xss64m) helps, but it is a patch, not a fix:

جیاوازییەکە . یەک چوارچێوە دووپاتە بەکار دەهێنێتەوە؛ بۆ هەر بانگکردنێکی چاوەڕوان چوارچێوەیەکی پێویستە. ⁦100,000⁩ بانگکردنی لە ناو یەک لە جێیان نابێتەوە، لە کاتێکدا سنووری نییە. شوێنی زیاتری (-Xss64m) یارمەتی دەدات، بەڵام پینەیە، نەک چارەسەر:

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

public class DeepSum {
    public static void main(String[] args) {
        System.out.println("loop:      " + sumLoop(100000));
        System.out.println("recursion: " + sum(100000));
    }

    static long sum(int k) {
        if (k <= 0) {
            return 0;
        }
        return k + sum(k - 1);
    }

    static long sumLoop(int k) {
        long total = 0;
        for (int i = 1; i <= k; i++) {
            total += i;
        }
        return total;
    }
}

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

java -Xss64m DeepSum

A loop reuses one frame; recursion needs one frame per call یەک چوارچێوە بەکار دەهێنێت؛ بۆ هەر بانگکردنێک یەکێکCêIT

Comparedبەراورد	Recursion	Loop
Codeکۆد	short when the problem contains smaller copies of itselfکورتە کاتێک کێشەکە وێنەی بچووکتری خۆی تێدایە	often a little longerزۆرجار کەمێک درێژترە
Memory	one frame per waiting callچوارچێوەیەک بۆ هەر بانگکردنێکی چاوەڕوان	one frameیەک چوارچێوە
Very deep problemsکێشەی زۆر قووڵ	`StackOverflowError`	no problemهیچ کێشە نییە
Best forباشترە بۆ	problems that branch: trees, folders in folders, search, merge sortکێشە لقدارەکان: ، لە ناو ، گەڕان، merge sort	counting, adding, repeating a fixed jobژماردن، کۆکردنەوە، دووپاتەکردنەوەی کارێکی دیاریکراو

Recursion shines when a problem branches: depth-first search (DFS and BFS) and the search of game trees are written recursively in the AI course. To see a loop version of factorial step by step, open the trace lab.

لەو شوێنانەدا دەدرەوشێتەوە کە کێشەیەک لق دەبێتەوە: (DFS و BFS) و گەڕان لە داری یارییەکاندا لە کۆرسی ژیریی دەستکرددا بە نووسراون. بۆ بینینی وەشانی هەنگاو بە هەنگاو، تاقیگەی بەدواداچوون بکەرەوە.

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

You wroteنووسیت	What happensچی ڕوو دەدات	Fixچارەسەر
no base caseبێ	`StackOverflowError`	Add one that answers without a call.یەکێک زیاد بکە کە بێ بانگکردن وەڵام بداتەوە.
`if (n == 0)`	with steps of 2 from an odd n: never trueبە هەنگاوی 2 لە nـی تاکەوە: هەرگیز ڕاست نابێت	Use `n <= 0`.`n <= 0` بەکار بهێنە.
`return f(n + 1);`	moves away from the base caseلە دوور دەکەوێتەوە	Make every call smaller: `n - 1`.هەموو بانگکردنێک بچووکتر بکە: `n - 1`.
`int s = k + sum(k - 1);`	`missing return statement`	`return k + sum(k - 1);return k + sum(k - 1);`
`int` for $13!$ `int` بۆ $13!$	a wrong number, no messageژمارەیەکی هەڵە، بێ پەیام	Use `long` (or BigInteger).`long` (یان BigInteger) بەکار بهێنە.
naive `fib(45)fib(45)`ـی ساکار	billions of callsملیاران بانگکردن	Use a loop. بەکار بهێنە.
recursion 100,000 deep بە قووڵیی ⁦100,000⁩	`StackOverflowError`	Use a loop. بەکار بهێنە.

The real message of row 4 — the recursive result is computed but never returned:

پەیامی ڕاستەقینەی 4 — ئەنجامی خۆبانگکەرانە دەدۆزرێتەوە بەڵام هەرگیز ناگەڕێتەوە:

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

public class SumMissingReturn {
    public static void main(String[] args) {
        System.out.println(sum(10));
    }

    static int sum(int k) {
        if (k <= 0) {
            return 0;
        }
        int s = k + sum(k - 1);
    }
}

Practiceڕاهێنان

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

Write static long power(int base, int exponent) by recursion, with power(b, 0) returning 1. Test $2^{10}$ , $3^4$ and $5^0$ .

static long power(int base, int exponent) بە بنووسە، کە power(b, 0) ژمارە 1 بگەڕێنێتەوە. $2^{10}$ ، $3^4$ و $5^0$ تاقی بکەرەوە.

Hintئاماژە

$b^e = b \times b^{e-1}$ : one multiplication, then a smaller exponent.

$b^e = b \times b^{e-1}$ : لێکدانێک، پاشان بچووکتر.

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

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

public class Power {
    public static void main(String[] args) {
        System.out.println(power(2, 10));
        System.out.println(power(3, 4));
        System.out.println(power(5, 0));
    }

    static long power(int base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        return base * power(base, exponent - 1);
    }
}

ExerciseڕاهێنانSum of the digitsکۆی تاکژمارەکان

Write static int digitSum(int n) for $n \ge 0$ by recursion: 2026 gives 10.

static int digitSum(int n) بۆ $n \ge 0$ بە بنووسە: ⁦2026⁩ دەبێتە ⁦10⁩.

Hintئاماژە

The last digit is n % 10; the rest is n / 10.

دوا n % 10ـە؛ باقییەکە n / 10ـە.

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

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

public class DigitSum {
    public static void main(String[] args) {
        System.out.println(digitSum(2026));
        System.out.println(digitSum(7));
        System.out.println(digitSum(99999));
    }

    static int digitSum(int n) {
        if (n < 10) {
            return n;
        }
        return n % 10 + digitSum(n / 10);
    }
}

ExerciseڕاهێنانGreatest common divisorگەورەترین بەشدراوی هاوبەش

Euclid's rule: $\gcd(a, 0) = a$ , and $\gcd(a, b) = \gcd(b,\ a \bmod b)$ , where $a \bmod b$ is a % b in Java. Write it recursively and test gcd(1071, 462).

یاسای ئیقلیدس: $\gcd(a, 0) = a$ و $\gcd(a, b) = \gcd(b,\ a \bmod b)$ ، کە $a \bmod b$ لە Javaـدا a % bـە. بە بینووسە و ⁦gcd(1071, 462)⁩ تاقی بکەرەوە.

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

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

public class Gcd {
    public static void main(String[] args) {
        System.out.println(gcd(1071, 462));
        System.out.println(gcd(48, 18));
        System.out.println(gcd(17, 5));
    }

    static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

1071 → 462 → 147 → 21 → 0: the second number shrinks fast, so only four calls are needed.

⁦1071⁩، ⁦462⁩، ⁦147⁩، ⁦21⁩، 0: ژمارەی دووەم خێرا بچووک دەبێتەوە، بۆیە تەنیا چوار بانگکردن پێویستە.

ExerciseڕاهێنانHow many calls?چەند بانگکردن؟

Without running it: how many calls does fib(6) make, counting itself? Then check with a counter.

بەبێ جێبەجێکردن: fib(6) چەند بانگکردن دەکات، بە خۆیەوە؟ پاشان بە پشکنینی بکە.

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

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

public class FibSix {
    static int calls = 0;

    public static void main(String[] args) {
        System.out.println("fib(6) = " + fib(6) + ", calls = " + calls);
    }

    static int fib(int n) {
        calls++;
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
}

$2 \times \text{fib}(7) - 1 = 2 \times 13 - 1 = 25$ calls.

$2 \times \text{fib}(7) - 1 = 2 \times 13 - 1 = 25$ بانگکردن.

ExerciseڕاهێنانBinary digitsتاکژمارەکانی دووانی

Write static void printBinary(int n) that prints n in binary, working on the way back like countUp. 13 is 1101 (Number systems).

static void printBinary(int n) بنووسە کە n بە چاپ بکات و وەک countUp لە ڕێگای گەڕانەوەدا کار بکات. ⁦13⁩ دەبێتە ⁦1101⁩ (سیستەمە ژمارەییەکان).

Hintئاماژە

Print the binary of n / 2 first, then n % 2.

سەرەتا n / 2 بە چاپ بکە، پاشان n % 2.

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

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

public class Binary {
    public static void main(String[] args) {
        printBinary(13);
        System.out.println();
        printBinary(2026);
        System.out.println();
    }

    static void printBinary(int n) {
        if (n >= 2) {
            printBinary(n / 2);
        }
        System.out.print(n % 2);
    }
}

ExerciseڕاهێنانReverse a wordپێچەوانەکردنەوەی وشەیەک

Write static String reverse(String text): the reverse of a text is the reverse of everything after the first letter, followed by the first letter (substring and charAt).

static String reverse(String text) بنووسە: پێچەوانەی دەقێک پێچەوانەی هەموو ئەوەیە کە دوای یەکەم پیت دێت، لەگەڵ یەکەم پیت لە دوایدا (substring و charAt).

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

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

public class Reverse {
    public static void main(String[] args) {
        System.out.println(reverse("Hawler"));
        System.out.println(reverse("level"));
        System.out.println("[" + reverse("") + "]");
    }

    static String reverse(String text) {
        if (text.length() <= 1) {
            return text;
        }
        return reverse(text.substring(1)) + text.charAt(0);
    }
}

Summaryکورتە

A recursive method calls itself with a smaller copy of the problem.
It needs a base case answered without a call, and every call must move closer to it.
Code before the recursive call runs on the way down; code after it runs on the way back.
Every waiting call keeps a frame on the call stack; with no (reachable) base case the stack overflows: StackOverflowError.
Factorials outgrow int at $13!$ ; naive Fibonacci repeats work (fib(40): 331,160,281 calls).
Any recursion can be a loop. Use recursion when a problem branches; use a loop for long, simple repetition.

خۆبانگکەر بە وێنەیەکی بچووکتری کێشەکە بانگی خۆی دەکاتەوە.
پێویستی بە هەیە کە بێ بانگکردن وەڵام بدرێتەوە و هەموو بانگکردنێک دەبێت نزیکتر بێتەوە لێی.
کۆدی پێش بانگکردنی خۆبانگکەرانە لە ڕێگای دابەزیندا جێبەجێ دەبێت؛ کۆدی دوای ئەو لە ڕێگای گەڕانەوەدا.
هەر بانگکردنێکی چاوەڕوان چوارچێوەیەک لەسەر دەهێڵێتەوە؛ بەبێ کە بانگکردنەکان پێی بگەن سەرڕێژ دەبێت: StackOverflowError.
لە $13!$ ـەوە لە int گەورەتر دەبن؛ فیبۆناچیی ساکار کار دووپاتە دەکاتەوە (⁦fib(40): 331,160,281⁩ بانگکردن).
هەموو دەکرێت بە . کاتێک کێشەیەک لق دەبێتەوە بەکار بهێنە؛ بۆ دووپاتەکردنەوەی درێژ و سادە .

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

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

The base case, answered directly, and the recursive case, which calls the method with a smaller problem.

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

What does a StackOverflowError usually mean?StackOverflowError زۆرجار چی دەگەیەنێت؟

Recursion that never reaches its base case (or is far too deep), so the call stack is full.

کە هەرگیز ناگاتە (یان زۆر قووڵە)، بۆیە پڕ بووە.

Why is recursive Fibonacci slow while recursive factorial is fast?بۆچی فیبۆناچیی خۆبانگکەر خاوە بەڵام فاکتۆریێلی خۆبانگکەر خێرایە؟

Fibonacci makes two calls each time and repeats the same work; factorial makes one call per step.

فیبۆناچی هەر جارێک دوو بانگکردن دەکات و هەمان کار دووپاتە دەکاتەوە؛ بۆ هەر هەنگاوێک یەک بانگکردن دەکات.

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

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

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

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

Packages, import and the Java APIپاکێجەکان، import و APIـی Java

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 ن.