Monash University > CSSE > CSE1303 > Part A > Lectures > Lecture A11 notes

CSE1303 Computer Science
Semester 3 (summer), 2003
Part A
Lecture A11 notes: Recursion

In this lecture

• Kruse 3.2 - 3.4
• Standish 3, 14
• Langsam 3

• Direct recursion, when a function calls itself.
• Indirect recursion, when a function calls other functions which then call it.
• Unary, where a function does a single recursive call.
• N-ary, where a function does n recursive calls.

1. A base case that is processed without recursion.
2. A general method that reduces a particular case to one or more simpler cases.

• Every time a function in C is called, its return address, its calling parameters, and its local variables are saved on the run-time stack.
• Every recursive function can be implemented using iteration and a stack.

• Since a recursive function will use the run-stack, it may use more space than an equivalent iterative procedure.
• Recursive functions, especially those which are applied to self-referential structures, maybe easier to write, and hence debug or change.

Code for this lecture

/*  This function returns x to the power of n.
 *  It also assumes that n is positive.  */
double power(double x, int n)
{
  int i;
  double tmp = 1;

  if (n > 0)
  {
    for (i = 0; i < n; i++)
    {
      tmp *= x;
    }
  }
  return tmp;
}

/*  This function returns x to the power of n.
 *  It also assumes that n is positive.  */
double power(double x, int n)
{
  double tmp = 1;

  if (n > 0)
  {
    tmp = power(x, n/2);
    if (n % 2 == 0)            /* n is even */
    {
      tmp = tmp*tmp;
    }
    else                       /* n is odd */
    {
      tmp = tmp*tmp*x;
    }
  }
  return tmp;
}

#include "linkList.h"

Node* copyNodes(Node* oldNodePtr);

/* This function copies an old linked list to a new one.  */
void copyList(List* newListPtr, List* oldListPtr)
{
  if (listEmpty(oldListPtr))
  {
    initializeList(newListPtr);
  }
  else
  {
    newListPtr->headPtr = copyNodes(oldListPtr->headPtr);
    newListPtr->count = oldListPtr->count;
  }
}

/*   This function recursively copies nodes from an old
 *   linked list into a new one.  */
Node* copyNodes(Node* oldNodePtr)
{
  Node* newNodePtr = NULL;

  if (oldNodePtr != NULL)
  {
    newNodePtr = makeNode(oldNodePtr->value);
    newNodePtr->nextPtr= copyNodes(oldNodePtr->nextPtr);
  }
  return newNodePtr;
}

#include "stack.h"

/*  An example of using a stack to implement recursion.  */
double power(double x, int n)
{
  double tmp = 1;
  Stack  theStack;

  initializeStack(&theStack);

  while (n != 0)
  {
    push(&theStack, n);
    n /= 2;
  }

  while (!stackEmpty(&theStack))
  {
    n = pop(&theStack);

    if (n % 2 == 0)
    {
      tmp = tmp * tmp;
    }
    else
    {
      tmp = tmp * tmp * x;
    }
  }
  return tmp;
}

int factorial ( int n )
{
  if ( n <= 1 )
  {
     return 1;
  }
  else
  {
     return n*factorial(n-1);
  }
}

long fib ( long n )
{
   if ( n <= 1 )
      return n ;
   else
      return fib( n - 2 ) + fib( n - 1 );
}

/* Delete the entire list (non recursive) */
void FreeList(Node* head){
  Node* next;

  while (head != NULL) {
    next=head->next;
    free(head);
    head=next;
  }
}

/* Delete the entire list (recursive) */
void FreeList(Node* list)
{
   if (list==NULL)
      return;
   FreeList(list->next);
   free(list);
}

[ Top | Home ]
Last Updated: Tuesday 02 December 2003 22:29:28