☰

Αναδρομικές συναρτήσεις (Recursion)

Γνωρίζουμε ότι μια συνάρτηση μπορεί να καλεί μια άλλη συνάρτηση η οποία (καλούμενη) συνήθως επιστρέφει ένα αποτέλεσμα (μια τιμή). Υπάρχει η περίπτωση όμως μια συνάρτηση να καλεί την ίδια συνάρτηση, δηλαδή να καλεί τον εαυτό της. Τότε η συνάρτηση αυτή λέγεται αναδρομική (recursive).

Σε συντομία, μια αναδρομική δείχνει όπως το παράδειγμα παρακάτω.

Παράδειγμα

void f() {
		f(); /* η συνάρτηση f καλεί την f */
	}

Οι αναδρομικές θέλουν ιδιαίτερη προσοχή διότι εύκολα μπορεί να ξεκινήσουμε έναν ατέρμονα βρόχο. Για αυτό υπάρχει μία συνθήκη που διακόπτει τις συνεχόμενες κλήσεις όταν η συνθήκη ικανοποιηθεί.

Στη συνέχεια δίνονται πρακτικά παραδείγματα όπου οι αναδρομικές συναρτήσεις βρίσκουν εφαρμογή.

Παράδειγμα

Υπολογισμός παραγοντικού ενός αριθμού.

#include <stdio.h>

	/* η αναδρομική συνάρτηση factorial υπολογίζει το παραγοντικό ενός αριθμού */
	int factorial(unsigned int i) {
		if(i <= 1) {
			return 1;
		}
		return i * factorial(i - 1);
	}

	int  main() {
		int f10 = factorial(10);
		printf("Παραγοντικό του 10: %d\n", f10);
		return 0;
	}

Παράδειγμα

Υπολογισμός σειράς Fibonacci. Στο παρακάτω παράδειγμα υπολογίζονται οι 10 πρώτοι αριθμοί από μια σειρά Fibonacci.

#include <stdio.h>

	int fibonacci(int i) {
		if(i == 0) {
			return 0;
		}
		if(i == 1) {
			return 1;
		}
		return fibonacci(i-1) + fibonacci(i-2);
	}

	int  main() {
		int i;
		for (i = 0; i < 10; i++) {
			printf("%d, ", fibonacci(i));
		}

		return 0;
	}