பாடம் 4 / 8 · Functions-ம் Arrays-ம் · படிக்க 3 min · புதுப்பிக்கப்பட்டது

Recursion

சின்ன பிரச்சனை மேல தன்னையே கூப்பிடுற function — அதை நிறுத்துற base case, ஒவ்வொரு call-ஐயும் வெச்சிருக்கிற stack.

Recursive function ஒரு பிரச்சனையை, அதோட சின்ன வடிவத்து மேல தன்னையே கூப்பிட்டு தீர்க்கும். ஒவ்வொரு recursive function-க்கும் ரெண்டு பகுதி வேணும்: நேரடியா பதில் சொல்ற base case, அதை நோக்கி நகர்ற recursive case.

c
#include <stdio.h>

int factorial(int n)
{
    if (n <= 1) {
        return 1;                  /* base case */
    }
    return n * factorial(n - 1);   /* recursive case */
}

int sum_digits(int n)
{
    if (n == 0) {
        return 0;
    }
    return n % 10 + sum_digits(n / 10);
}

int main(void)
{
    printf("5! = %d\n", factorial(5));
    printf("sum of digits of 4127 = %d\n", sum_digits(4127));
    return 0;
}
Output
5! = 120
sum of digits of 4127 = 14
ஒவ்வொரு call-ம் சின்ன call-க்காக stack-ல காத்திருக்கும். factorial(1) 1-ன்னு பதில் சொல்லும், பதில்கள் திரும்ப பெருகி வரும்: 1, 2, அப்புறம் 6.

Fibonacci series

c
#include <stdio.h>

int fib(int n)
{
    if (n < 2) {
        return n;                        /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void)
{
    for (int i = 0; i < 10; i++) {
        printf("%d ", fib(i));
    }
    printf("\n");
    return 0;
}
Output
0 1 1 2 3 5 8 13 21 34

Warning

Base case இல்லன்னா — இல்லன்னா அதை எப்பவுமே எட்டலன்னா, உதாரணமா n == 1 test-ஓட factorial(-1) கூப்பிட்டா — calls நிக்கவே நிக்காது, stack நிரம்பி program stack overflow-ஓட crash ஆகும். எப்பவும் base case-ஐ முதல்ல check பண்ணுங்க.

Note

Recursion loop-ஐ விட வேகமானது இல்ல — இப்படி fib(40) கூப்பிட்டா கோடிக்கணக்கான calls நடக்கும். பிரச்சனை இயல்பாவே தன்னைப் போலவே இருந்தா use பண்ணுங்க: tree structures, folder-க்குள்ள folder, divide-and-conquer sorting. சாதாரண எண்ணிக்கைக்கு loop தான் நல்லது.

நிக்கணும்னா ஒவ்வொரு recursive function-லயும் என்ன இருக்கணும்?

இப்போ இதை செஞ்சு பாருங்க

  1. Recursive power(base, exp) எழுதுங்க: power(2, 10) 1024 தரணும்.
  2. ஒரு number-ஓட digits-ஐ தலைகீழா print பண்ற recursive function எழுதுங்க: 4127 → 7214.
  3. n-ல இருந்து 1 வரைக்கும் எண்ணி, அப்புறம் "Go!" print பண்ற recursive function எழுதுங்க.

Create a free account to save your progress, or sign in.