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) ;
}