Show description
CSE 240 Module 5 - Recursion & Data Structures Cheat Sheet
CSE 240 Module 5 - Recursion & Data Structures Cheat Sheet
CSE 240 Module 5
Recursion & Data Structures Cheat Sheet
Table of Contents
1. Recursion Basics
2. The Fantastic Four Approach
3. Sorting Algorithms
4. Hanoi Towers
5. Trees and Graphs
6. Binary Search Trees
7. Complexity Analysis
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
CSE 240 Module 5 - Recursion & Data Structures Cheat Sheet
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>CSE 240 Module 5 - Recursion & Data Structures Cheat Sheet</title>
<style>
* {
margin: 0;
padding: 0;
box-sizing: border-box;
}
body {
font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif;
line-height: 1.6;
background-color: #ffffff;
color: #333;
padding: 20px;
max-width: 1200px;
margin: 0 auto;
}
.header {
text-align: center;
margin-bottom: 30px;
padding: 20px;
background: linear-gradient(135deg, #1e3c72, #2a5298);
color: white;
border-radius: 10px;
box-shadow: 0 4px 6px rgba(0,0,0,0.1);
}
.header h1 {
font-size: 2.5em;
margin-bottom: 10px;
}
.header p {
font-size: 1.2em;
opacity: 0.9;
}
.section {
margin-bottom: 30px;
padding: 20px;
border: 2px solid #2a5298;
border-radius: 10px;
background-color: #f8f9ff;
}
.section-title {
font-size: 1.8em;
color: #1e3c72;
margin-bottom: 15px;
padding-bottom: 10px;
border-bottom: 3px solid #2a5298;
}
.subsection {
margin-bottom: 20px;
padding: 15px;
background-color: white;
border-left: 4px solid #2a5298;
border-radius: 5px;
}
.subsection h3 {
color: #2a5298;
margin-bottom: 10px;
font-size: 1.3em;
}
.code-block {
background-color: #f4f4f4;
border: 1px solid #ddd;
border-radius: 5px;
padding: 15px;
margin: 10px 0;
font-family: 'Courier New', monospace;
overflow-x: auto;
border-left: 4px solid #2a5298;
}
.formula {
background-color: #e8f2ff;
border: 2px solid #2a5298;
border-radius: 5px;
padding: 10px;
margin: 10px 0;
text-align: center;
font-weight: bold;
color: #1e3c72;
}
.step-box {
background-color: #e8f2ff;
border: 2px solid #2a5298;
border-radius: 8px;
padding: 15px;
margin: 10px 0;
}
.step-number {
display: inline-block;
background-color: #2a5298;
color: white;
border-radius: 50%;
width: 30px;
height: 30px;
text-align: center;
line-height: 30px;
margin-right: 10px;
font-weight: bold;
}
.complexity-table {
width: 100%;
border-collapse: collapse;
margin: 15px 0;
background-color: white;
}
.complexity-table th, .complexity-table td {
border: 1px solid #2a5298;
padding: 12px;
text-align: center;
}
.complexity-table th {
background-color: #2a5298;
color: white;
font-weight: bold;
}
.complexity-table tr:nth-child(even) {
background-color: #f8f9ff;
}
.highlight {
background-color: #e8f2ff;
padding: 2px 4px;
border-radius: 3px;
font-weight: bold;
color: #1e3c72;
}
.tree-diagram {
text-align: center;
font-family: monospace;
background-color: #f9f9f9;
padding: 15px;
border: 1px solid #ddd;
border-radius: 5px;
margin: 10px 0;
}
.button {
display: inline-block;
padding: 10px 20px;
background-color: #2a5298;
color: white;
text-decoration: none;
border-radius: 5px;
margin: 5px;
border: none;
cursor: pointer;
font-size: 14px;
}
.button:hover {
background-color: #1e3c72;
}
.two-column {
display: grid;
grid-template-columns: 1fr 1fr;
gap: 20px;
margin: 15px 0;
}
@media (max-width: 768px) {
.two-column {
grid-template-columns: 1fr;
}
}
.key-points {
background-color: #fff3cd;
border: 1px solid #ffeaa7;
border-left: 4px solid #fdcb6e;
padding: 15px;
margin: 10px 0;
border-radius: 5px;
}
.toc {
background-color: #f8f9ff;
border: 2px solid #2a5298;
border-radius: 10px;
padding: 20px;
margin-bottom: 30px;
}
.toc h2 {
color: #1e3c72;
margin-bottom: 15px;
}
.toc ul {
list-style-type: none;
}
.toc li {
margin: 8px 0;
}
.toc a {
color: #2a5298;
text-decoration: none;
font-weight: 500;
}
.toc a:hover {
text-decoration: underline;
}
</style>
</head>
<body>
<div class="header">
<h1>CSE 240 Module 5</h1>
<p>Recursion & Data Structures Cheat Sheet</p>
</div>
<div class="toc">
<h2>Table of Contents</h2>
<ul>
<li><a href="#recursion-basics">1. Recursion Basics</a></li>
<li><a href="#fantastic-four">2. The Fantastic Four Approach</a></li>
<li><a href="#sorting">3. Sorting Algorithms</a></li>
<li><a href="#hanoi">4. Hanoi Towers</a></li>
<li><a href="#trees">5. Trees and Graphs</a></li>
<li><a href="#bst">6. Binary Search Trees</a></li>
<li><a href="#complexity">7. Complexity Analysis</a></li>
</ul>
</div>
<div id="recursion-basics" class="section">
<h2 class="section-title">1. Recursion Basics</h2>
<div class="subsection">
<h3>What is Recursion?</h3>
<p>A function (or procedure) is <span class="highlight">recursive</span> if it calls itself within the function.</p>
<div class="key-points">
<strong>Key Point:</strong> There's a special type called <span class="highlight">tail-recursion</span> which calls itself only once and in the last statement. Tail recursion is very similar to a do-while loop.
</div>
</div>
<div class="subsection">
<h3>Factorial Example</h3>
<div class="formula">
n! = {1 if n = 0, 1*2*3*...*(n-1)*n if n > 0}
</div>
<div class="formula">
Recursive: n! = {1 if n = 0, (n-1)!*n if n > 0}
</div>
<div class="two-column">
<div>
<h4>Iterative Solution:</h4>
<div class="code-block">int Factorial(int n) {
int fact = 1;
for(int count = 2; count <= n; count++)
fact = fact * count;
return fact;
}</div>
</div>
<div>
<h4>Recursive Solution:</h4>
<div class="code-block">int Factorial(int n) {
if (n==0) return 1;
else return n * Factorial(n-1);
}</div>
</div>
</div>
</div>
<div class="subsection">
<h3>Structure Comparison</h3>
<div class="tree-diagram">
<strong>While-Loop vs Recursion vs Tail-Recursion</strong><br><br>
While: condition → loop-body → jump back<br>
Recursion: condition → part 1 → recursive call → part 2<br>
Tail-Recursion: condition → part 1 → recursive call
</div>
</div>
</div>
<div id="fantastic-four" class="section">
<h2 class="section-title">2. The Fantastic Four Abstract Approach</h2>
<div class="subsection">
<h3>Four-Step Method for Writing Recursive Functions</h3>
<div class="step-box">
<span class="step-number">1</span>
<strong>Formulate the size-n problem</strong>
<ul>
<li>Recursion is necessary when we need to repeat operations multiple times</li>
<li>Choose a function name and use n as the parameter</li>
<li>Example: <code>int factorial(int n)</code></li>
<li>We do NOT design the solution in this step</li>
</ul>
</div>
<div class="step-box">
<span class="step-number">2</span>
<strong>Find the stopping condition and corresponding return value</strong>
<ul>
<li>Like a while-loop, recursive function starts with checking stopping condition</li>
<li>If true, return the corresponding value and exit</li>
<li>Example: factorial stopping condition is <code>n = 0</code>, return value is <code>1</code></li>
</ul>
</div>
<div class="step-box">
<span class="step-number">3</span>
<strong>Formulate the size-m problem (m < n)</strong>
<ul>
<li>Replace n with m, where m < n</li>
<li>Usually m = n-1, but application-specific</li>
<li>Don't define solution here, just assume it returns a value</li>
<li>Example: assume <code>factorial(n-1)</code> returns a value</li>
</ul>
</div>
<div class="step-box">
<span class="step-number">4</span>
<strong>Construct solution from size-m problem</strong>
<ul>
<li>Use the assumed solution from step 3</li>
<li>Example: <code>n * factorial(n-1)</code></li>
<li>Sometimes need multiple size-m problems (like merge sort)</li>
</ul>
</div>
</div>
</div>
<div id="sorting" class="section">
<h2 class="section-title">3. Sorting Algorithms</h2>
<div class="subsection">
<h3>Insertion Sort using Fantastic Four</h3>
<div class="step-box">
<span class="step-number">1</span>
<strong>Size-n problem:</strong> <code>int* sorting(int *A, int n);</code>
</div>
<div class="step-box">
<span class="step-number">2</span>
<strong>Stopping condition:</strong> n == 1, return address of A
</div>
<div class="step-box">
<span class="step-number">3</span>
<strong>Size-m problem:</strong> m = n-1, assume first n-1 elements sorted
</div>
<div class="step-box">
<span class="step-number">4</span>
<strong>Solution:</strong> Insert element x at correct position in sorted array
</div>
</div>
<div class="subsection">
<h3>Time Complexity Comparison</h3>
<table class="complexity-table">
<thead>
<tr>
<th>Sorting Algorithm</th>
<th>Average-case</th>
<th>Worst-case</th>
</tr>
</thead>
<tbody>
<tr>
<td>Insertion Sort</td>
<td>O(n²) - Slow</td>
<td>O(n²)</td>
</tr>
<tr>
<td>Mergesort</td>
<td>O(n lg n) - Fast</td>
<td>O(n lg n)</td>
</tr>
<tr>
<td>Quicksort</td>
<td>O(n lg n) - Fastest</td>
<td>O(n²)</td>
</tr>
</tbody>
</table>
</div>
</div>
<div id="hanoi" class="section">
<h2 class="section-title">4. Hanoi Towers</h2>
<div class="subsection">
<h3>Problem Description</h3>
<p>Move n disks from source to destination using center as temporary, following rules:</p>
<ul>
<li>Only move one disk at a time</li>
<li>Larger disk cannot be placed on smaller disk</li>
</ul>
</div>
<div class="subsection">
<h3>Recursive Solution</h3>
<div class="code-block">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
}
}</div>
</div>
<div class="subsection">
<h3>Following the Four Steps</h3>
<div class="step-box">
<span class="step-number">1</span>
<strong>Size-n:</strong> <code>void Hanoi(n, source, center, destination)</code>
</div>
<div class="step-box">
<span class="step-number">2</span>
<strong>Stopping:</strong> n = 1, "Move disk from source to destination"
</div>
<div class="step-box">
<span class="step-number">3</span>
<strong>Size-(n-1):</strong> Two cases needed for this problem
</div>
<div class="step-box">
<span class="step-number">4</span>
<strong>Solution:</strong> Move n-1 to center, move bottom to dest, move n-1 from center to dest
</div>
</div>
</div>
<div id="trees" class="section">
<h2 class="section-title">5. Trees and Graphs</h2>
<div class="subsection">
<h3>Basic Definitions</h3>
<ul>
<li><strong>Linked List:</strong> Each node has one next-node</li>
<li><strong>Graph:</strong> More than one next node allowed</li>
<li><strong>Tree:</strong> A graph with no loops and no more than one path between any two nodes</li>
<li><strong>Height (Depth):</strong> Number of edges from root to deepest leaf</li>
</ul>
</div>
<div class="subsection">
<h3>Binary Trees</h3>
<ul>
<li><strong>Binary Tree:</strong> Any node can have at most two next nodes (child nodes)</li>
<li><strong>Full Binary Tree:</strong> Each node has either no child or two children</li>
<li><strong>Balanced Binary Tree:</strong> Heights of any two leaf nodes never differ by more than 1</li>
<li><strong>Height of n-node balanced tree:</strong> O(log₂n)</li>
</ul>
</div>
</div>
<div id="bst" class="section">
<h2 class="section-title">6. Binary Search Trees (BST)</h2>
<div class="subsection">
<h3>Data Structure Definition</h3>
<div class="code-block">struct treeNode {
int data; // also called key
struct treeNode *left, *right; // pointers to treeNode
}
struct treeNode *root = NULL; // global pointer to root</div>
</div>
<div class="subsection">
<h3>Tree Traversal Algorithms</h3>
<div class="two-column">
<div>
<h4>Inorder Traversal</h4>
<div class="code-block">inorderTraverse(p) {
if p ≠ 0 then
inorderTraverse(p->left);
print(p->data);
inorderTraverse(p->right);
}</div>
<p><strong>Result:</strong> left subtree - root - right subtree</p>
</div>
<div>
<h4>Preorder Traversal</h4>
<div class="code-block">preorderTraverse(p) {
if p ≠ 0 then
print(p->data);
preorderTraverse(p->left);
preorderTraverse(p->right);
}</div>
<p><strong>Result:</strong> root - left subtree - right subtree</p>
</div>
</div>
<div class="key-points">
<strong>Postorder:</strong> left subtree - right subtree - root<br>
<strong>Analogy:</strong> Tree postorder = print after recursive calls, Linked list preorder = print forward, postorder = print backward
</div>
</div>
<div class="subsection">
<h3>Search Function</h3>
<div class="code-block">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;
}</div>
</div>
<div class="subsection">
<h3>Insertion Algorithm</h3>
<div class="code-block">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; i<n; i++) {
p = (struct treeNode *) malloc(sizeof(struct treeNode));
key = rand() % 100; // random key
p->data = 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;
}
}
}</div>
</div>
</div>
<div id="complexity" class="section">
<h2 class="section-title">7. Complexity Analysis Summary</h2>
<div class="subsection">
<h3>Search Algorithm Complexity</h3>
<ul>
<li><strong>Linear search:</strong> O(n) for data in arrays or linked lists</li>
<li><strong>Binary search:</strong> O(log₂n) if the binary tree is balanced</li>
<li><strong>Unbalanced BST:</strong> Could degenerate to O(n) (like a linked list)</li>
</ul>
</div>
<div class="subsection">
<h3>Improving Search Speed</h3>
<ul>
<li><strong>Make tree balanced:</strong> Requires restructuring (Red-Black tree)</li>
<li><strong>Allow more children:</strong> k-ary search tree with O(log_k n) performance</li>
<li><strong>Best performance:</strong> Google BigTable uses advanced tree structures</li>
</ul>
</div>
<div class="key-points">
<strong>Remember:</strong> 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.
</div>
</div>
<div style="text-align: center; margin-top: 40px; padding: 20px; background-color: #f8f9ff; border-radius: 10px;">
<p style="color: #2a5298; font-weight: bold;">CSE 240 - Introduction to Programming Languages | Arizona State University</p>
<p style="color: #666; font-size: 0.9em;">This cheat sheet covers Module 5: Recursion and Data Structures</p>
</div>
</body>
</html>