Rekursio C:ssä

Rekursio on tekniikka, jossa funktio kutsuu itseään ongelman ratkaisemiseksi.

Tässä oppitunnissa opitte:

• Mitä rekursio on ja miten se toimii.
• Miten rekursiivisia funktioita toteutetaan.
• Miten rekursio ja iteraatio eroavat toisistaan.

Rekursiossa funktio kutsuu itseään ratkaistakseen ongelman pienemmän osan.

Esimerkkisyntaksi:

void function() { function(); // Recursive call }

Jokaisella rekursiivisella funktiolla on oltava perustapaus, joka estää rekursion jatkumisen loputtomasti.

Tämä ohjelma havainnollistaa rekursiota tulostamalla luvut 5–1.

#include <stdio.h>

void countDown(int n) {
    if (n <= 0) return; // Base case
    printf("%d\n", n);
    countDown(n - 1); // Recursive call
}

int main() {
    countDown(5);
    return 0;
}

Rekursiiviseen funktioon on sisällytettävä perustapaus rekursion lopettamiseksi.

Esimerkki:

if (n == 0) return;

Ilman perustapausta funktio kutsuu itseään loputtomasti, mikä aiheuttaa pinon ylivuodon.

Tämä ohjelma laskee luvun kertoman rekursion avulla.

#include <stdio.h>

int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1);
}

int main() {
    printf("Factorial of 5: %d\n", factorial(5));
    return 0;
}

Rekursiolla ja iteraatiolla (silmukoilla) voidaan saavuttaa sama tulos, mutta ne toimivat eri tavoin.

Erot:

• Rekursio käyttää funktiokutsuja ja vaatii enemmän muistia.
• Iteraatio käyttää silmukoita ja on yleensä tehokkaampaa.
• Rekursio tekee koodista yksinkertaisempaa esimerkiksi puun läpikäynnissä.

Tämä ohjelma laskee Fibonaccin lukujonon rekursion avulla.

#include <stdio.h>

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

int main() {
    printf("Fibonacci(5): %d\n", fibonacci(5));
    return 0;
}

Rekursio on hyödyllinen ongelmissa, joihin liittyy:

• Puun läpikäynti.
• Peruutushaku (esimerkiksi sokkeloiden ratkaiseminen).
• Matemaattiset ongelmat, kuten kertoma ja Fibonacci.

Tässä oppitunnissa opitte:

• Mitä rekursio on ja miten se toimii.
• Perustapauksen tärkeyden.
• Rekursion ja iteroinnin välisen eron.

Seuraavaksi tutustumme C-kielen taulukoihin ja merkkijonoihin!