Recursion: any function that calls itself is called recursive (all other functions are referred to as non-recursive).
int getPositiveInteger() { // prompt the user printf("Please enter a positive integer\n"); // read in the value int value; scanf("%d", &value); // if it is valid return it if (value > 0) return value; // otherwise // give an error message // call the function again // store what comes back and return it else { printf("Error: %d was not a positive integer\n", value); value = getPositiveInteger(); return value; } } |
In the example below we sum the contents of an array from array positions 0 through N-1. The 'simple' (or 'base') case is where N is less than 1, where all we need to do is return 0 (don't sum anything). For all other cases we make a recursive call to get the sum of the previous N-1 elements and add the current element to the result (returning that).
int sumArray(int arr[], int N) { int value; // simplest case, sum nothing if (N < 1) value = 0; } else { // call the function to sum the previous N-1 elements value = sumArray(arr[], N-1); // and add the Nth element to that value = value + arr[N-1]; } // return the result return value; } |
int smallest(int arr[], int N) { int result if (N == 1) result = arr[0]; else { // compare smallest thing from first N-1 elements // to the Nth element, return whichever is smaller result = smallest(arr, N-1); if (result > arr[N-1]) result = arr[N-1]; } return result; } |
int fibonacci(int N) { if (N <= 0) return 0; else if (N == 1) return 1; else return (fibonacci(N-1) + fibonacci(N-2)); } |
int getPositiveInteger() { static int count = 0; count++; printf("Entering getPosInt call %d\n", count); printf("Please enter a positive integer\n"); int value, result; scanf("%d", &value); if (value > 0) result = value; else { printf("Error: %d was not a positive integer\n", value); result = getPositiveInteger(); } printf("Leaving getPosInt call %d", count); printf(", returning %d\n", result); return result; } | int sumArray(int arr[], int N) { int value; printf("In sumArray, N = %d\n", N); if (N < 1) value = 0; } else { value = sumArray(arr[], N-1); value = value + arr[N-1]; } printf("In sumArray, N = %d", N); printf(", returning %d\n", value); return value; } |
int smallest(int arr[], int N) { int result printf("In smallest, N = %d\n", N); if (N == 1) result = arr[0]; else { result = smallest(arr, N-1); if (result > arr[N-1]) result = arr[N-1]; } printf("In smallest, N = %d", N); printf(", returning %d\n", result); return result; } | int fibonacci(int N) { int value = 0; if (N <= 0) value = 0; else if (N == 1) value = 1; else { printf( "inside call fib(%d), calling fib(%d)\n", N, N-1); value = fibonacci(N-1); printf("inside call fib(%d), calling fib(%d)\n", N, N-2); value += fibonacci(N-2); } printf("call fib(%d) completing\n", N); return value; } |
original program #include <cstdio> int f1(int a); int f2(int b); int main() { printf("main: %d\n", f1(2)); } int f1(int a) { int result = a; printf("entering f1: %d\n", result); if (a >= 0) result = f2(a+1); printf("leaving f1: %d\n", result); return result; } int f2(int b) { int result = b; printf("entering f2:%d\n", result); if (b >= 0) result = f1(b-2); printf("leaving f2:%d\n", result); return result; } | output produced entering f1:2 entering f2:3 entering f1:1 entering f2:2 entering f1:0 entering f2:1 entering f1:-1 leaving f1:-1 leaving f2:-1 leaving f1:-1 leaving f2:-1 leaving f1:-1 leaving f2:-1 leaving f1:-1 main:-1 |