Recursion P.J. Drongowski 5 November 2004 Recursion * C++ (and other modern programming languages) permit a function to call itself -- a so-called "recursive function" * Recursion is a very effective means to concisely express certain algorithms * It is sometimes easier to write a formula recursively than to write it as a closed form expression * List and tree manipulations are quite compatible with recursion * Other uses: search, expression parsing Recursion and induction * Recursion is based upon the idea of induction in mathematics -- that a function can be defined in terms of two cases: + A base case, where the value of the function is defined for fixed values of one or more of its parameters; it is a case that can be solved without recursion + An inductive case, where the value of the function is defined in terms of previous values of the function * Inductive proof can be used to show that a recursive function is mathematically correct [Main and Savitch] 1. Show that there is no infinite recursion 2. Show that the base case is correct (i.e., satisfies the desired mathematical property) 3. Show that the current recursive call is correct when previous calls are also correct (induction step) Recursive functions in practice * Bookkeeping + Calls are tracked on the runtime call stack + A call stack is a natural way to handle nesting + Each call creates a "frame" on the stack, so there is one frame per level of recursion * Infinite recursion occurs when successive calls to the same function are made without stopping * Infinite recursion is bad -- the stack fills up and the program runs out of memory * A base case is needed to prevent infinite recursion -- it is the stopping condition * The inductive case must lead or converge to the base case by systematically changing the parameters passed to the recursive calls - the inductive step must make progress Classic example #1: Factorial * Base case: When n = 1, factorial(1) = 1 * Inductive case: factorial(n) = factorial(n-1) * n int factorial(int n) { if (n == 1) { return( 1 ) ; } else { return( factorial(n-1) * n ) ; } } * Note that factorial decreases the value of n by one with each recursive call, such that the calls will lead to the base case Classic example #2: Recursive power (x to the n) * Base case: When n = 0, power(x, n) = 1 * Inductive case: power(x, n) = power(x, n-1) * x int power(int x, int n) { if (n == 0) { return( 1 ) ; } else { return( power(x, n-1) * x ) ; } } * Note that n must be greater or equal to zero. This function will attempt infinite recursion if n is less than zero. Classic example #3: Fibonacci numbers * 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... * Named after Italian mathematician Leonardo Fibonacci * Base cases: fibonacci(1) = 1, fibonacci(2) = 1 * Inductive case: fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) int fibonacci(int n) { if (n <= 2) { return( 1 ) ; } else { return( fibonacci(n-1) + fibonacci(n-2) ) ; } } * Computing Fibonacci numbers this way is not particularly efficient. Why? F5 / \ Trace of recursive computation / \ of Fibanacci number F5 / \ F4 F3 / \ /\ / \ F2 F1 / \ /\ F3 F2 F1 F0 /\ /\ F2 F1 F1 F0 /\ F1 F0 Classic example #4: Printing a decimal number (n >= 0 ) * Base case: When n < 10, output n * Inductive case: print_num(n / 10), output (n % 10) void print_num(int n) { if (n < 10) { cout << n ; } else { print_num(n / 10) ; cout << (n % 10) ; } } Classic example #5: Sum of integers in an array (n >= 0) * Base case: When n = 0, sum(array, n) = array[0] * Inductive case: sum(array, n) = sum(array, n-1) + array[n] int sum(int array[], int n) { if (n == 0) return( array[0] ) ; else { return( sum(array, n-1) + array[n] ) ; } } * Is this an efficient way to compute a sum? Classic example #6: Greatest common divisor (GCD) * Given two nonnegative integers N and M, the greatest common divisor of M and N is the largest integer D that divides both M and N * Euclid's algorithm: gcd(M, N) = gcd(M-N, N) + If D divides both M and N, then D must also divide M-N + If D divides both M-N and N, then it must also divide M + Repeatedly subtract N from M; when N becomes less than M, switch roles + When N becomes zero, then gcd(M,0) = M + Repeated subtraction can be replaced by modulus operation * Base case: gcd(M,0) = M * Inductive case: gcd(M,N) = gcd(N, M % N) int gcd(int M, int N) { if (N == 0) return( M ) ; else { return( gcd(N, M % N) ) ; } } Classic example #7: Ackermann's function * Base cases: + If m = 0, then A(m,n) = n+1 + If n = 0, then A(m,n) = A(m-1,1) * Inductive case: A(m,n) = A(m-1, A(m,n-1)) Direct and indirect recursion * If a function calls itself directly, this is called "direct recursion" * If function f calls another function g, and g calls f, this is called "indirect recursion" (The number of intermediate functions may vary) Efficiency * Recursive algorithms are less efficient than iterative algorithms + Extra time needed for function call + Extra space needed for frame on call stack * Design decisions + Is a problem more easily solved using recursion? A loop? + Is a solution more easily understood and maintained using recursion? + Does the function use large local arrays? + Does the algorithm deal with linear structures? Nested structures? Branching? Tail recursion * A function uses tail recursion if the last statement in the function is the recursive call * The function returns immediately after the recursive call * Tail recursion can be transformed into iteration by replacing the recursive call with a branch (jump) back to the beginning of the function * It may be necessary to add a stack to remember previous results *************************************************************** Recursive list operations: recur_list.h *************************************************************** #ifndef RECUR_LIST_H #define RECUR_LIST_H class Node { friend class List ; public: int data ; Node *next ; Node() { data = 0 ; next = NULL ; } } ; typedef Node *PtrNode ; class List { public: List() ; // List constructor List(const List &old) ; // Copy constructor ~List() ; // Destructor void prepend(int value) ; // Add node to front void append(int value) ; // Add node to end void print() ; // Display the list private: PtrNode first ; int length ; PtrNode List::inner_append(PtrNode list, int value) ; void inner_print(PtrNode pList) ; } ; #endif *************************************************************** Recursive list operations: recur_list.cpp *************************************************************** #include #include using namespace std ; #include "recur_list.h" List::List() { first = NULL ; length = 0 ; } ... PtrNode List::inner_append(PtrNode list, int value) { PtrNode pNew ; if (list == NULL) { pNew = new Node() ; pNew->data = value ; pNew->next = NULL ; return( pNew ) ; } else { list->next = inner_append(list->next, value) ; return( list ) ; } } void List::append(int value) { first = inner_append(first, value) ; length += 1 ; } void List::inner_print(PtrNode pList) { if (pList == NULL) return ; else { cout << pList->data << endl ; inner_print(pList->next) ; } } void List::print() { inner_print(first) ; }