Recursive Functions
A recursive function is a function that calls itself! What do you think the following will do?
void message(void); int main(void){
message();
return EXIT_FAILURE; }
void message(void){
printf(“Good Evening.”);
printf(“Are you happy with your phone plan?”); message();
}
’Infinite’ recursion
Similar to how we can have infinite loops (iteration) which will happily run forever, such as
int i =0;
while ( i < n ){
printf("Good evening.");
printf("Are you happy with your phone plan?");
}
the program on the previous slide was an example of infinite recursion.
However, infinite recursion will eventualy end with a segmentation fault. Why?
Recursive Functions
We can slightly modify our infinitely recursive program to run a given number of times in the following way:
void message(int n); int main(void){
message(5);
return EXIT_FAILURE; }
void message(void){ if ( n > 0 ){
} }
printf(“Good Evening.”);
printf(“Are you happy with your phone plan?”);
message();
Recursive Functions
Recursion is useful when problems can be expressed in terms of a simpler instance of the same problem.
For example: factorial
1! = 1
2! = 2 * 1 = 2 * 1!
3! = 3 * 2 * 1 = 3 * 2!
.
.
.
n! = n * n-1 * … * 1 = n * (n-1)!
Recursive Functions
A recursive function must include:
• Base Case (aka Stopping case) : Where no recursive call is needed
• Recursive Case: Calls the function on a simpler version of the problem
Recursion vs Iteration
//Iterative factorial function (could also use a for loop)
int factorial(int n){ int result = 1; while( n > 0 ){
result *= n;
n–; }
return result; }
//Recursive factorial function
int factorial(int n){ if ( n <= 1 ){
return 1; } else {
//Stopping Case
}
return n * factorial(n-1); //Recursive Case }
Recursive Factorial and the Stack
We keep calling factorial and pushing stack frames onto the stack
for each call until we reach the stopping case, 1.
The stack frame for factorial(1)
can be removed and the return value of 1 can be used by factorial(2). Then the stack frame for factorial(2) can be removed and its return value of 2 can be used by factorial(3) and so on.
Linked Lists and Recursion
We can also use recursion instead of iteration to write linked list functions.
We can think of a linked list recursively in the following way: A linked list is comprised of:
• a head (node)
• a tail (the rest of the list)
Summing a List with Iteration
// return sum of list data fields
int sum(struct node *head) { int sum = 0;
struct node *n = head;
// execute until end of list while (n != NULL) {
sum += n->data;
// make n point to next item n = n->next;
}
return sum; }
Summing a List with Recursion
Same function but using a recursive call.
Compiler will produce same machine code as previous function.
// return sum of list data fields
int sum(struct node *head) { if (head == NULL) {
return 0; }
return head->data + sum(head->next); }
Finding an Item in a List with Iteration
// return pointer to first node containing
// specified value, return NULL if no such node struct node *findNode(struct node *head, int data) {
struct node *n = head;
// search until end of list reached while (n != NULL) {
if (n->data == data) { return n;
}
n = n->next; }
// item not in list
return NULL; }
Finding an Item in a List: Recursive
Same function but function calls itself
Good compiler will produce same machine code as previous functions.
// return pointer to first node containing
// specified value, return NULL if no such node struct node *findNode(struct node *head, int data) {
if (head == NULL) { return NULL;
}
if (head->data == data) {
return head; }
return findNode(head->next, data); }
Finding an Item in a List: Shorter Recursive
Same function but a more consise recursive version. Shorter does not always mean more readable.
Good compiler will produce same machine code as previous functions.
// return pointer to first node containing
// specified value, return NULL if no such node
struct node *findNode(struct node *head, int data) { if (head == NULL || head->data == data) {
return head; }
return findNode(head->next, data); }
Print a List: Iterative
// print contents of list
void printList(struct node *head) {
for (struct node *n = head; n != NULL; n = n->next) {
printf(“%d”, n->data);
}
printf(“\n”); }
Print a List: Recursive
// print contents of list
void printList(struct node *head) { printNodes(head);
printf(“\n”); }
void printNodes(struct node *head) { if( head != NULL ){
} }
printf(“%d”, head->data);
//Recursive call is AFTER the call to print printNodes(head->next);
Print a List Backwards: Recursive
// print contents of list
void printListBackwards(struct node *head) { printNodesBackwards(head); printf(“\n”);
}
//This is harder to do with iteration. We would need //to do something tricky, or use a doubly linked list //or write our own stack!
void printNodesBackwards(struct node *head) {
if( head != NULL ){
//Recursive call is BEFORE the call to print printNodesBackwards(head->next); printf(“%d”, head->data);
} }