Show description
The Art of Recursion
The Art of Recursion
The Art of Recursion
What is Recursion? 🤔
Recursion is a powerful programming technique where a function calls itself to solve a problem. Think of it like a set of Russian nesting dolls; each doll contains a smaller, identical version of itself, until you get to the final, smallest doll that can't be opened.
Every recursive solution has two essential parts:
The Base Case: This is the "smallest doll." It's the simplest version of the problem that can be solved directly, without making another recursive call. The base case acts as the stopping condition. Without it, you get infinite recursion and a stack overflow error!
The Recursive Step: This is where the magic happens. The function breaks the current problem down into a slightly smaller version of itself and calls itself to solve that smaller piece. It then combines the result of that call to solve the original problem.
Why Use It?
While anything you can do with recursion you can also do with loops (iteration), recursion is preferred when it leads to a simpler, more elegant solution. It shines when working with data structures that are themselves defined recursively, like trees and linked lists. It's also the cornerstone of the functional programming paradigm.
Factorial Examples Across Languages
The factorial function is the "Hello, World!" of recursion. Let's see how it's implemented in a few different languages you're studying in CSE 240 and beyond.…
The Art of Recursion
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>The Art of Recursion</title>
<style>
/* --- Red, Black & White Theme --- */
:root {
--bg-color: #121212; /* Near black for the background */
--text-color: #f0f0f0; /* Off-white for readability */
--primary-red: #e50914; /* A vibrant, modern red */
--header-font: 'Helvetica Neue', sans-serif;
--body-font: 'Georgia', serif;
--code-font: 'Fira Code', 'Courier New', monospace;
}
body {
background-color: var(--bg-color);
color: var(--text-color);
font-family: var(--body-font);
line-height: 1.6;
margin: 0;
padding: 2rem;
}
.container {
max-width: 900px;
margin: 0 auto;
padding: 2rem;
background-color: #1c1c1c;
border: 1px solid var(--primary-red);
border-radius: 8px;
box-shadow: 0 0 20px rgba(229, 9, 20, 0.3);
}
h1, h2, h3 {
font-family: var(--header-font);
color: var(--primary-red);
border-bottom: 2px solid var(--primary-red);
padding-bottom: 10px;
letter-spacing: 1px;
text-transform: uppercase;
}
h1 {
text-align: center;
font-size: 2.5rem;
}
p {
margin-bottom: 1rem;
}
strong, b {
color: var(--primary-red);
}
pre {
background-color: #0d0d0d;
border: 1px solid #444;
border-left: 5px solid var(--primary-red);
padding: 1.5em;
border-radius: 5px;
overflow-x: auto;
white-space: pre-wrap;
word-wrap: break-word;
}
code {
font-family: var(--code-font);
background-color: #2b2b2b;
padding: 0.2em 0.4em;
border-radius: 3px;
font-size: 0.95em;
}
pre code {
background-color: transparent;
padding: 0;
border-radius: 0;
font-size: 1em;
}
footer {
text-align: center;
margin-top: 3rem;
color: #888;
}
</style>
</head>
<body>
<div class="container">
<header>
<h1>The Art of Recursion</h1>
</header>
<main>
<section id="what-is-recursion">
<h2>What is Recursion? 🤔</h2>
<p>
Recursion is a powerful programming technique where a function calls itself to solve a problem. Think of it like a set of Russian nesting dolls; each doll contains a smaller, identical version of itself, until you get to the final, smallest doll that can't be opened.
</p>
<p>
Every recursive solution has two essential parts:
</p>
<ul>
<li><strong>The Base Case:</strong> This is the "smallest doll." It's the simplest version of the problem that can be solved directly, without making another recursive call. The base case acts as the stopping condition. <strong>Without it, you get infinite recursion and a stack overflow error!</strong></li>
<li><strong>The Recursive Step:</strong> This is where the magic happens. The function breaks the current problem down into a slightly smaller version of itself and calls itself to solve that smaller piece. It then combines the result of that call to solve the original problem.</li>
</ul>
</section>
<hr>
<section id="why-recursion">
<h2>Why Use It?</h2>
<p>
While anything you can do with recursion you can also do with loops (iteration), recursion is preferred when it leads to a simpler, more elegant solution. It shines when working with data structures that are themselves defined recursively, like trees and linked lists. It's also the cornerstone of the <strong>functional programming paradigm</strong>.
</p>
</section>
<hr>
<section id="code-examples">
<h2>Factorial Examples Across Languages</h2>
<p>
The factorial function is the "Hello, World!" of recursion. Let's see how it's implemented in a few different languages you're studying in CSE 240 and beyond. The goal is to calculate <code>n!</code>.
</p>
<article>
<h3>C++</h3>
<pre><code>#include <iostream>
// The classic recursive implementation in C++
int factorial(int n) {
// Base Case: 0! is 1
if (n == 0) {
return 1;
}
// Recursive Step: n * (n-1)!
else {
return n * factorial(n - 1);
}
}
int main() {
std::cout << "5! is " << factorial(5) << std::endl; // Output: 120
return 0;
}</code></pre>
</article>
<article>
<h3>Scheme</h3>
<p>In Scheme, recursion is the primary way to perform iteration.</p>
<pre><code>; define the factorial procedure
(define (factorial n)
; Base Case: if n is 0, the result is 1
(if (= n 0)
1
; Recursive Step: n * (factorial of n-1)
(* n (factorial (- n 1)))))
; call the procedure
(display (factorial 5)) ; Output: 120
(newline)</code></pre>
</article>
<article>
<h3>Prolog</h3>
<p>In Prolog, recursion is expressed as rules that refer to themselves.</p>
<pre><code>% Base Case: The factorial of 0 is 1.
factorial(0, 1).
% Recursive Step: The factorial of N is F if...
factorial(N, F) :-
N > 0,
N1 is N - 1, % Calculate N-1
factorial(N1, F1), % Recursively find the factorial of N-1
F is N * F1. % F is N times the result.
% Query:
% ?- factorial(5, Result).
% Result = 120.</code></pre>
</article>
<article>
<h3>Python</h3>
<pre><code>def factorial(n):
# Base Case
if n == 0:
return 1
# Recursive Step
else:
return n * factorial(n - 1)
print(f"5! is {factorial(5)}") # Output: 120</code></pre>
</article>
<article>
<h3>Java</h3>
<pre><code>public class RecursionExample {
public static int factorial(int n) {
// Base Case
if (n == 0) {
return 1;
}
// Recursive Step
else {
return n * factorial(n - 1);
}
}
public static void main(String[] args) {
System.out.println("5! is " + factorial(5)); // Output: 120
}
}</code></pre>
</article>
<article>
<h3>Go</h3>
<pre><code>package main
import "fmt"
func factorial(n int) int {
// Base Case
if n == 0 {
return 1
}
// Recursive Step
return n * factorial(n-1)
}
func main() {
fmt.Printf("5! is %d\n", factorial(5)) // Output: 120
}</code></pre>
</article>
<article>
<h3>Rust</h3>
<pre><code>fn factorial(n: u64) -> u64 {
// Base Case
if n == 0 {
1
}
// Recursive Step (no explicit return needed for the last expression)
else {
n * factorial(n - 1)
}
}
fn main() {
println!("5! is {}", factorial(5)); // Output: 120
}</code></pre>
</article>
</section>
</main>
<footer>
<p>Created for a CSE 240 student. Keep crushing it!</p>
</footer>
</div>
</body>
</html>