Recursion: যে function নিজেকেই call করে

Module 7-এ Bob শিখেছে, একটা function যেকোনো function-কে call করতে পারে। তারপর মাথায় একটা সাহসী প্রশ্ন আসে: function কি নিজেকেই call করতে পারে? ওর দরকার 1 + 2 + 3, আর ও খেয়াল করে, এটা আসলে 3 যোগ 1 + 2।

তাই ও এমন একটা function লেখে, যেটা n-এর সাথে n - 1-এর জন্য নিজেরই উত্তর যোগ করে। তারপর Run চাপে। কিছুই আসে না। 10 সেকেন্ড পরে Playground program-টা থামিয়ে দেয়, আর badge-এ লেখা ওঠে টাইম লিমিট পার হয়েছে।

ওর বইতে লেখা ছিল, এমন ভুলে নাটকীয় একটা "stack overflow" হবে। ও পেল শুধু চুপচাপ একটা ঘড়ি। Bob কোন লাইনটা বাদ দিয়েছে, আর ওই 10 সেকেন্ডে আসলে কী ঘটেছে, এই lesson সেটাই খুঁজে বের করবে।

Recursion: যে function নিজেকেই call করে

যে function নিজেকেই call করে, তাকে বলে recursive, আর পুরো ধারণাটার নাম recursion। এটা কাজ করে তখনই, যখন প্রতিটা call একই সমস্যার একটা ছোট রূপ পরের call-এর হাতে তুলে দেয়। Bob ঠিক যেভাবে run করেছিল, ওর program-টা এই:

#include <stdio.h>

int sum_to(int n);

int main(void)
{
    printf("%d\n", sum_to(3));
    return 0;
}

int sum_to(int n)
{
    return n + sum_to(n - 1);
}

হাতে একবার trace করে দেখো। sum_to(3)-এর লাগে sum_to(2), সেটার লাগে sum_to(1), আর সেটার লাগে sum_to(0)। sum_to(0)-কে থামতে কেউ বলে না, তাই সে চায় sum_to(-1), তারপর sum_to(-2), এভাবে শেষই হয় না।

টিকিট কাউন্টারের একটা লম্বা লাইনের কথা ভাবো। তুমি কত নম্বরে আছ জানতে চাও, তাই সামনের জনকে জিজ্ঞেস করো, আর তার উত্তরের সাথে এক যোগ করো। সে-ও একই কাজ করে। এই শিকল থামে একদম সামনের জনের কাছে গিয়ে: সে কাউকে জিজ্ঞেস না করেই জানে, সে 1 নম্বর।

তাই recursive function-এ এমন একটা call লাগবেই, যেটা কাউকে জিজ্ঞেস না করেই উত্তর দেয়। Bob-এর program-এ প্রতিটা call শুধু জিজ্ঞেসই করে, উত্তর দেয় না কেউ।

দুইটা নিয়ম: base case আর step

যে recursive function শেষ হয়, সেটা দুইটা নিয়ম মানে। Base case হলো সবচেয়ে ছোট input, যার উত্তর সরাসরি দেওয়া হয়, কোনো call ছাড়া। Step একই function-কে একটা ছোট input দিয়ে call করে, base case-এর দিকে এক ধাপ এগিয়ে। কোনো কোনো বই step-কে বলে recursive case।

type name(int n)
{
    if (n == smallest) {
        return answer;
    }
    return ... name(n - 1) ...;
}

Bob হারানো নিয়মটা যোগ করে। 0 পর্যন্ত সংখ্যার যোগফল তো 0, তাই sum_to(0) কোনো call ছাড়াই 0 return করে। সাথে ও উত্তরটাকে long long বানায়, কারণ n = 65536 থেকে যোগফল INT_MAX পার হয়ে যায়।

#include <stdio.h>

long long sum_to(int n);

int main(void)
{
    printf("%lld\n", sum_to(3));
    printf("%lld\n", sum_to(100));
    return 0;
}

long long sum_to(int n)
{
    if (n == 0) {
        return 0;
    }
    return n + sum_to(n - 1);
}

Run করার আগে trace করো। Module 6-এ loop trace হতো প্রতিটা pass-এর জন্য এক সারি দিয়ে। Recursion-এ সারি হয় প্রতিটা call-এর জন্য একটা: call-টা, তার parameter, সে কীসের অপেক্ষায়, আর কী return করে। একে বলা যায় frame table।

Table-টা দুই দফায় ভরো। Call যেমন যেমন হয়, প্রথম তিনটা কলাম উপর থেকে নিচে ভরে যাও। তারপর শেষ কলামটা ভরো নিচ থেকে উপরে: নিচের সারি return না করা পর্যন্ত উপরের সারি শেষই হতে পারে না।

6
5050

তার মানে উত্তর শুরু হয় base case থেকেই। Bob-এর program-এর মতো base case না থাকলে কোনো সারি কখনো return করে না।

Countdown: call-এর আগের কাজ

Module 6-এর সেই rocket game-এ Bob-এর countdown-টা আবার লাগবে, এবার recursion দিয়ে। n থেকে countdown মানে: n বলো, তারপর n - 1 থেকে countdown করো। আর 0 থেকে countdown মানে শুধু "liftoff"।

#include <stdio.h>

void countdown(int n);

int main(void)
{
    countdown(3);
    return 0;
}

void countdown(int n)
{
    if (n == 0) {
        printf("liftoff\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);
}

3
2
1
liftoff

প্রতিটা call আগে print করে, পরে call করে, তাই সংখ্যাগুলো আসে ঠিক সেই ক্রমে, যে ক্রমে call হয়। একদম নিচে base case print করে liftoff। void function কোনো মান return করে না, তাই ওর base case শেষ হয় শুধু return; দিয়ে।

তাই call-এর আগে রাখা কাজ হয় নামার পথে, call-গুলো যে ক্রমে হয় সেই ক্রমেই।

Call-এর পরের কাজ হয় ফেরার পথে

এবার কাজটা call-এর নিচে বসাও। Call-এর পরের লাইন ততক্ষণ run হতে পারে না, যতক্ষণ না ওই call return করছে। তাই call-এর পরের লাইনগুলো run হয় উল্টো ক্রমে, ফেরার পথে।

Alice দেখতে চায়, sum_to ধাপে ধাপে কীভাবে উত্তর বানায়। ও প্রতিটা যোগফল একটা local variable-এ রাখে, আর call-এর পরে সেটা print করে।

#include <stdio.h>

long long sum_to(int n);

int main(void)
{
    long long total = sum_to(3);

    printf("total: %lld\n", total);
    return 0;
}

long long sum_to(int n)
{
    long long total = 0;

    if (n == 0) {
        return 0;
    }
    total = n + sum_to(n - 1);
    printf("sum to %d is %lld\n", n, total);
    return total;
}

Call হয় উপরের সারি থেকে নিচের দিকে, কিন্তু print হয় নিচের সারি থেকে উপরের দিকে। সবার আগে print করে sum_to(1), কারণ উত্তর সবার আগে ওর হাতেই আসে।

sum to 1 is 1
sum to 2 is 3
sum to 3 is 6
total: 6

প্রতিটা call নিজের parameter আর local variable-এর জন্য নিজস্ব বাক্স পায় (Module 7)। এই বাক্সগুলো মিলে হয় call-টার frame। যে call-গুলো এখনো অপেক্ষায়, ওদের frame জমতে থাকে memory-র একটা অংশে, যার নাম stack, প্রতি call-এ একটা করে। Stack খুলে দেখাবে lesson 2; এখানে ছবিটা দেখো।

বাঁ দিকের তীরগুলো call, নামার পথে। ডান দিকের তীরগুলো উত্তর, ফেরার পথে। কোনো call return করলে ওর frame-টা মুছে যায়।

তাই call-এর আগের কাজ চলে বাঁ দিকের তীর ধরে, আর পরের কাজ চলে ডান দিকের তীর ধরে।

Factorial, long long দিয়ে

Module 6 তোমার কাছে Kenji-র factorial চেয়েছিল একটা loop দিয়ে, আর কথা দিয়েছিল ওটা আবার ফিরবে। n-এর factorial, লেখা হয় n!, মানে 1 x 2 x ... x n, আর 0! হলো 1। এবার recursion-এর চোখে পড়ো: n! মানে n গুণ (n - 1)!, আর 0! হলো base case।

#include <stdio.h>

long long factorial(int n);

int main(void)
{
    for (int i = 0; i <= 20; i++) {
        printf("%d! = %lld\n", i, factorial(i));
    }
    return 0;
}

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

ওই call-গুলোর একটা, factorial(4), তার frame table এরকম:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000

উত্তর খুব দ্রুত বাড়ে। 12! = 479001600 একটা int-এ এঁটে যায়, কিন্তু 13! = 6227020800 পার হয়ে যায় INT_MAX, মানে 2147483647। এজন্যই factorial return করে long long।

long long-এর দৌড় 20! পর্যন্ত। LLONG_MAX হলো 9223372036854775807, আর 20! তার মোটামুটি চার ভাগের এক ভাগ। 21! হলো 20!-এর 21 গুণ, প্রায় 5.1 x 10^19, মানে LLONG_MAX-এর পাঁচ গুণেরও বেশি। ওটা হিসাব করতে গেলেই signed overflow, যেটা undefined behaviour (Module 2), তাই এই lesson ওটা কখনো print করে না।

তাই recursive factorial-এর লাগে base case 0! = 1, আর উত্তর ধরার মতো বড় একটা type: 12! পর্যন্ত int, 20! পর্যন্ত long long।

Base case না থাকলে কী হয়, মেপে দেখা

আবার Bob-এর program-এ ফিরি। ওর বই বলে, base case ছাড়া function "Stack overflow" error দেখায়। C এমন কোনো বার্তা print করে না, আর Playground-এ Bob-এর program crash-ই করেনি। কারণটা দেখো।

Playground compile করে GCC 12 দিয়ে, -O2-তে, আর সেটা optimise করে। মানে তোমার program-কে একই কাজের দ্রুততর machine code হিসেবে নতুন করে লেখে। GCC 12 দেখেছে, প্রতিটা call পরের call-এর উত্তরের সাথে শুধু একটা সংখ্যা যোগ করে। তাই ও call-গুলোর জায়গায় একটা loop বসিয়ে দিয়েছে, আর সেই loop থেকে বেরোনোর কোনো পথ নেই।

এই machine code-কে বলে listing। Compiler Explorer-এ, Playground-এর -O2-তে, GCC 12 যেটা print করেছে সেটা এই:

main:
.L2:
        jmp     .L2
sum_to:
.L5:
        jmp     .L5

jmp .L2 মানে ".L2 label-এ লাফ দাও", আর .L2 ঠিক এই লাইনটাই। তাই main চিরকাল নিজের জায়গাতেই লাফাতে থাকে, নিজের printf পর্যন্ত কখনো পৌঁছায় না। কোনো call বাকি নেই, কিছু জমেও না, program শুধু ঘুরতে থাকে, যতক্ষণ না 10 সেকেন্ডের limit আসে।

তুমি কী দেখবে, সেটা নির্ভর করে function-টা নিজের call-এর আশপাশে কী করে তার উপর:

বাংলা Playground page-এ Memory limit-এর badge-টা বাংলায় দেখায়, ফাঁকা output-এর লেখাটাও।

Machine code build-এর উপরও নির্ভর করে। Bob-এর file optimisation ছাড়া build করো, -O0-তে, তাহলে প্রতিটা call একটা আসল frame পায়। Compiler Explorer-এর GCC 12-এ একবার run করে দেখা গেছে, ওই build 193 ms-এই crash করে, আর বলে Program terminated with signal SIGSEGV (11)।

Linux terminal-এ একই crash print করে Segmentation fault। কোনো program যে memory ছোঁয়ার অনুমতি পায়নি সেটা ছুঁলে, operating system এভাবেই জানায়। Signal আর stack-এর সীমার কথা আসবে lesson 5-এ।

এর কোনো ফলেই recursion-এর নাম নেই, তবে compiler নামটা বলতে পারে। Playground চুপ থাকে। নিজের মেশিনে GCC 12-এর gcc -Wall বলে warning: infinite recursion detected [-Winfinite-recursion], সাথে একটা note, যেটা দেখিয়ে দেয় call-টা কোথায়। এই warning GCC 12-এ নতুন।

তাই base case না থাকলে সেটা দেখতে time limit, output error বা memory limit-এর মতো লাগতে পারে। Run করার আগেই -Wall আসল সমস্যার নাম বলে দেয়।

#include <stdio.h>

void stars(int n);

int main(void)
{
    stars(3);
    printf("\n");
    return 0;
}

void stars(int n)
{
    if (n == 0) {
        return;
    }
    printf("*");
    stars(n - 1);
}

***

#include <stdio.h>

long long pyramid(int layers);

int main(void)
{
    printf("4 layers: %lld oranges\n", pyramid(4));
    printf("10 layers: %lld oranges\n", pyramid(10));
    return 0;
}

long long pyramid(int layers)
{
    if (layers == 0) {
        return 0;
    }
    return layers * layers + pyramid(layers - 1);
}

4 layers: 30 oranges
10 layers: 385 oranges

#include <stdio.h>

long long sum_range(int a, int b);

int main(void)
{
    int a = 0;
    int b = 0;

    scanf("%d %d", &a, &b);
    printf("%lld\n", sum_range(a, b));
    return 0;
}

long long sum_range(int a, int b)
{
    if (a > b) {
        return 0;
    }
    return a + sum_range(a + 1, b);
}

25

long long every_other(int n)
{
    if (n == 0) {
        return 0;
    }
    return n + every_other(n - 2);
}

long long sum_to(int n)
{
    if (n == 0) {
        return 0;
    }
    n + sum_to(n - 1);
}

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

#include <stdio.h>

void f(int n);

int main(void)
{
    f(3);
    printf("\n");
    return 0;
}

void f(int n)
{
    if (n == 0) {
        return;
    }
    f(n - 1);
    printf("%d ", n);
}

#include <stdio.h>

long long sum_to(int n);

int main(void)
{
    int n = 0;
    scanf("%d", &n);

    printf("%lld\n", sum_to(n));
    return 0;
}

long long sum_to(int n)
{
    /* The base case comes first: what is the sum of the numbers up to 0?
       Then return n plus one call with a smaller n. */
    return 0;
}

#include <stdio.h>

long long factorial(int n);

int main(void)
{
    int n = 0;

    while (scanf("%d", &n) == 1) {
        printf("%lld\n", factorial(n));
    }
    return 0;
}

long long factorial(int n)
{
    /* The base case comes first. Which n is the smallest one allowed?
       Every other n is n times the factorial of n - 1. */
    return 0;
}

#include <stdio.h>

void down_and_up(int n);

int main(void)
{
    int n = 0;
    scanf("%d", &n);

    down_and_up(n);
    return 0;
}

void down_and_up(int n)
{
    /* One function that prints on both sides of its own call.
       How many times must 1 be printed? */
}

এরপর Amara কাগজে frame আঁকে, প্রতি call-এ একটা বাক্স, আর Run চাপার আগেই output বলে দেয়।