REKURSSIO

Funktio voi kutsua myös itseään, tätä kutsutaan rekursioksi. Rekursiivinen kutsu voi olla joko suora tai epäsuora. Suoralla rekursiolla tarkoitetaan tilannetta, jossa funktiota kutsutaan funktion omassa määrittelyssä ja epäsuoralla rekursiolla tilannetta, jossa funktiota kutsuu käyttämällä toista funktiota (tai useita), joka sisältää funktiota kutsuneen funktion kutsun.
Ongelmat, joita rekursion avulla ratkaistaan, ovat sellaisia, joissa funktion saamia tietoja käsitellään samalla tavalla kuin funktion tuottamaa tulostakin. Erityisesti rekursio sopii dynaamisten tietorakenteiden käyttöön. Rekursiivisissa funktioissa piilee myös vaaroja. On oltava tarkkana, että rekursio päättyy jossakin vaiheessa tai muuten on seurauksena ajoaikainen virhe. Toisaalta ajonaikainen kutsupino saattaa täyttyä, mikäli käsitellään isoja rakenteita.

Esim.

/* Ohjelmassa etsitään n:s luku Fibonaccin sarjasta Algoritmi: fib(n) = fib(n - 2) + fib(n - 1) Lopetusehto: n = 2 || n = 1 Ratkaisussa käytetään rekursiota.*/ #include <stdio.h> int fib(int n); /* pääohjelma, jossa kutsutaan rekursiivista funktiota */ void main() { int n, vastaus; printf("Anna etsittävän luvun positio\n"); scanf("%d", &n); vastaus = fib(n); printf("\n\nFibonaccin sarjan %d luku on %d\n", n, vastaus); } int fib(int n) { printf("Lasketaan fib %d ...",n); if (n < 3) { printf("Palautetaan 1 !\n"); return (1); } else { printf("Tehdään kutsut fib(%d) ja fib(%d)\n", n-2, n-1); return (fib(n-2) + fib(n-1)); } }




Esim.

/* Ohjelma korottaa luvun potenssiin */ #include <stdio.h> long power(int x, int n); int main(void) { int kanta, ekspon; long potenssi; scanf(”%d %d”, &kanta, &ekspon); potenssi = power(kanta, ekspon); printf(”%d potenssiin %d on %ld\n”, kanta, ekspon, potenssi); return 0; } long power(int x, int n) { if (n == 0) return 1; else return x*power(x, n - 1); }




MERKKIJONO - JA MERKKIFUNKTIOT

Otsikkotiedosto string.h määrittelee funktiot, jotka käsittelevät merkkijoukkoja. C-kielessä ei ole merkkijonotyyppiä joten yhden merkkijonon arvoa ei voi sijoittaa toisen merkkijonon arvoksi.

char a[23]; char b[23] = ”Mahdoton sijoitus”; a = b; /* ei mahdollinen sijoitusoperaatio */

Ohjelmassa on käytettävä funktioita, jotka kopioivat yhden merkkijonon sisällön toiseen merkkijonoon.

#include <string.h> ............. char a[23]; char b[23]; strcpy(a, b); /* Tämä on mahdollista */

Otsikkotiedoston string.h sisältämiä funktioita:

funktio kuvaus strcmp() vertaa kahta merkkijonoa strlen() palauttaa merkkijonon pituuden strcat() lisää yhden merkkijonon toiseen strcpy() kopioi yhden merkkijonon toiseen

HUOM! Mahdollisesti edellä mainittuja ei ole Dev C++ kääntäjässä C-kieli-osassa käytettävissä.