CSE 240 Module 5

1. Recursion Basics

What is Recursion?

A function (or procedure) is recursive if it calls itself within the function.

Key Point: There's a special type called tail-recursion which calls itself only once and in the last statement. Tail recursion is very similar to a do-while loop.

Factorial Example

n! = {1 if n = 0, 1*2*3*...*(n-1)*n if n > 0}

Recursive: n! = {1 if n = 0, (n-1)!*n if n > 0}

Iterative Solution:

int Factorial(int n) {
    int fact = 1;
    for(int count = 2; count <= n; count++)
        fact = fact * count;
    return fact;
}

Recursive Solution:

int Factorial(int n) {
    if (n==0) return 1;
    else return n * Factorial(n-1);
}

Structure Comparison

While-Loop vs Recursion vs Tail-Recursion

While: condition → loop-body → jump back
Recursion: condition → part 1 → recursive call → part 2
Tail-Recursion: condition → part 1 → recursive call

2. The Fantastic Four Abstract Approach

Four-Step Method for Writing Recursive Functions

1 Formulate the size-n problem

Recursion is necessary when we need to repeat operations multiple times
Choose a function name and use n as the parameter
Example: int factorial(int n)
We do NOT design the solution in this step

2 Find the stopping condition and corresponding return value

Like a while-loop, recursive function starts with checking stopping condition
If true, return the corresponding value and exit
Example: factorial stopping condition is n = 0, return value is 1

3 Formulate the size-m problem (m < n)

Replace n with m, where m < n
Usually m = n-1, but application-specific
Don't define solution here, just assume it returns a value
Example: assume factorial(n-1) returns a value

4 Construct solution from size-m problem

Use the assumed solution from step 3
Example: n * factorial(n-1)
Sometimes need multiple size-m problems (like merge sort)

3. Sorting Algorithms

Insertion Sort using Fantastic Four

1 Size-n problem: int* sorting(int *A, int n);

2 Stopping condition: n == 1, return address of A

3 Size-m problem: m = n-1, assume first n-1 elements sorted

4 Solution: Insert element x at correct position in sorted array

Time Complexity Comparison

Sorting Algorithm	Average-case	Worst-case
Insertion Sort	O(n²) - Slow	O(n²)
Mergesort	O(n lg n) - Fast	O(n lg n)
Quicksort	O(n lg n) - Fastest	O(n²)

4. Hanoi Towers

Problem Description

Move n disks from source to destination using center as temporary, following rules:

Only move one disk at a time
Larger disk cannot be placed on smaller disk

Recursive Solution

void hanoitowers(int n, char *S, char *M, char *D) {
    if (n == 1) {
        cout << "move top from " << S << " to " << D << endl;
    }
    else {
        hanoitowers(n - 1, S, D, M); // size-(n-1) problem
        hanoitowers(1, S, M, D);     // size-1 problem  
        hanoitowers(n - 1, M, S, D); // size-(n-1) problem
    }
}

Following the Four Steps

1 Size-n: void Hanoi(n, source, center, destination)

2 Stopping: n = 1, "Move disk from source to destination"

3 Size-(n-1): Two cases needed for this problem

4 Solution: Move n-1 to center, move bottom to dest, move n-1 from center to dest

5. Trees and Graphs

Basic Definitions

Linked List: Each node has one next-node
Graph: More than one next node allowed
Tree: A graph with no loops and no more than one path between any two nodes
Height (Depth): Number of edges from root to deepest leaf

Binary Trees

Binary Tree: Any node can have at most two next nodes (child nodes)
Full Binary Tree: Each node has either no child or two children
Balanced Binary Tree: Heights of any two leaf nodes never differ by more than 1
Height of n-node balanced tree: O(log₂n)

6. Binary Search Trees (BST)

Data Structure Definition

struct treeNode {
    int data;           // also called key
    struct treeNode *left, *right; // pointers to treeNode
}
struct treeNode *root = NULL;  // global pointer to root

Tree Traversal Algorithms

Inorder Traversal

inorderTraverse(p) {
    if p ≠ 0 then
        inorderTraverse(p->left);
        print(p->data);
        inorderTraverse(p->right);
}

Result: left subtree - root - right subtree

Preorder Traversal

preorderTraverse(p) {
    if p ≠ 0 then
        print(p->data);
        preorderTraverse(p->left);
        preorderTraverse(p->right);
}

Result: root - left subtree - right subtree

Postorder: left subtree - right subtree - root
Analogy: Tree postorder = print after recursive calls, Linked list preorder = print forward, postorder = print backward

Search Function

struct treeNode * search(struct treeNode *top, int key) {
    struct treeNode *p = top;
    if (key == p->data)
        printf("data = %d\n", p->data);
    if (key < p->data) {
        if (p->left == NULL) return p;
        else return search(p->left, key);
    }
    else {
        if (p->right == NULL) return p;
        else return search(p->right, key);
    }
    return p;
}

Insertion Algorithm

void insertion() {
    struct treeNode *p, *q;
    int i, n, key;
    printf("Enter the number of entries you want to insert\n");
    scanf("%d", &n);
    for (i=0; idata = key;
        p->left = NULL; p->right = NULL;
        if (root == NULL) root = p;  // tree empty
        else {
            q = search(root, key);
            if (key <= q->data) q->left = p;
            else q->right = p;
        }
    }
}

7. Complexity Analysis Summary

Search Algorithm Complexity

Linear search: O(n) for data in arrays or linked lists
Binary search: O(log₂n) if the binary tree is balanced
Unbalanced BST: Could degenerate to O(n) (like a linked list)

Improving Search Speed

Make tree balanced: Requires restructuring (Red-Black tree)
Allow more children: k-ary search tree with O(log_k n) performance
Best performance: Google BigTable uses advanced tree structures

Remember: The choice between recursion and iteration often depends on the problem structure. Recursion is elegant for tree operations and divide-and-conquer algorithms, while iteration might be more efficient for simple repetitive tasks.

Table of Contents