Recursion
Recursion is a programming technique in which a function solves a problem by calling itself on smaller subproblems, combined with a base case that stops the recursive calls and prevents infinite repetition.
70 resources across 4 libraries
Glossary Terms(16)
Pascal
Pascal is a procedural, statically typed programming language created by Niklaus Wirth in the early 1970s, designed to encourage structured, disciplined progra…
Prolog
Prolog is a declarative, logic-based programming language in which programs are expressed as facts and rules, and computation proceeds by the language's engine…
Scheme
Scheme is a minimalist dialect of Lisp, created in the mid-1970s by Gerald Jay Sussman and Guy Steele, known for its small, elegant core syntax and emphasis on…
Racket
Racket is a general-purpose, multi-paradigm programming language descended from Scheme, originally released as PLT Scheme, designed with particular emphasis on…
AWK
AWK is a classic Unix programming language and command-line tool, created in 1977 by Alfred Aho, Peter Weinberger, and Brian Kernighan, designed for scanning a…
Sed
Sed (stream editor) is a classic Unix command-line utility for parsing and transforming text non-interactively, applying editing commands like substitution, de…
Haskell
Haskell is a purely functional, statically typed programming language named after logician Haskell Curry, distinguished by lazy evaluation, strong type inferen…
Functional Programming
Functional programming is a programming paradigm that treats computation as the evaluation of pure functions, emphasizing immutability, avoidance of side effec…
Procedural Programming
Procedural programming is a programming paradigm that structures code as a sequence of step-by-step instructions organized into procedures (or functions), whic…
Recursion
Recursion is a programming technique in which a function solves a problem by calling itself on smaller subproblems, combined with a base case that stops the re…
Big O Notation
Big O notation is a mathematical notation used in computer science to describe how an algorithm's running time or memory usage grows as the size of its input i…
Linked List
A linked list is a linear data structure made up of nodes, where each node stores a value and a reference (pointer) to the next node in the sequence, allowing…
Dynamic Programming
Dynamic programming (DP) is an algorithmic technique for solving problems by breaking them into overlapping subproblems, solving each subproblem once, and stor…
Sorting Algorithm
A sorting algorithm is a procedure that rearranges the elements of a list or array into a defined order, typically ascending or descending, and is one of the m…
Graph Algorithm
A graph algorithm is a procedure that operates on a graph — a set of nodes (vertices) connected by edges — to solve problems such as finding shortest paths, de…
Memoization
Memoization is an optimization technique that caches the results of expensive function calls so that when the same inputs occur again, the cached result is ret…
Study Notes(15)
Recursion in Pascal
Learn how Pascal functions and procedures can call themselves, and how to design correct base cases and recursive cases.
Recursion in LISP
Understand how recursion works in LISP, including base cases, recursive list processing, and tail-call optimization.
Recursion and loop/recur
Learn how Clojure handles recursion without mutable loop variables, and how the recur special form enables safe, stack-efficient tail recursion via loop and fu…
Recursion and Tail Calls
Understand how F# uses recursion instead of mutable loops, and how tail-call optimization lets recursive functions run in constant stack space.
Recursion in Erlang
Why recursion replaces loops in Erlang, and how to write correct, tail-recursive functions that run in constant stack space.
Recursion and Enum
Explore how Elixir uses recursion for iteration and how the Enum and Stream modules provide higher-level functions built on that foundation.
Recursion in Haskell
Understand why recursion is the primary looping mechanism in Haskell, how base cases and recursive cases work, and how tail recursion and laziness affect perfo…
Recursion in Assembly
See how recursive functions are implemented at the machine level using the call stack, and why stack depth and register preservation matter.
Recursive Bash Functions
Learn how to write Bash functions that call themselves safely, including base cases, stack limits, and when recursion is (and isn't) the right tool.
Recursion in C++
Understand how recursive functions call themselves, why a base case is required, and the risk of stack overflow without one.
Recursion in C
Master recursion in C: base case, recursive case, call-stack tracing, factorial example, and avoiding stack overflow.
Recursion in Python
Writing recursive functions with proper base cases, understanding the call stack, and avoiding RecursionError from missing base cases or excessive depth.
Recursion Basics
Learn how functions that call themselves can solve problems by breaking them into smaller subproblems.
Recursion Trees and Recurrence Relations
Model the runtime of recursive algorithms as recurrence relations and solve them by drawing recursion trees.
Recursion vs Iteration
Compare recursive and iterative solutions in terms of clarity, performance, memory usage, and when to prefer each.
Cheat Sheets(2)
Interview Questions(37)
What is Recursion?
Recursion is a technique where a function solves a problem by calling itself on a smaller instance of the same problem, until it reaches a base case that stops…
BFS vs DFS: What is the Difference?
BFS (breadth-first search) explores a graph level by level using a queue, while DFS (depth-first search) explores as deep as possible along one path before bac…
Merge Sort vs Quick Sort: What is the Difference?
Merge sort splits an array in half, recursively sorts both halves, then merges them, guaranteeing O(n log n) time and stability at the cost of O(n) extra space…
What is Memoization?
Memoization is an optimization technique that caches the results of expensive function calls keyed by their arguments, so repeated calls with the same inputs r…
What is Backtracking?
Backtracking is a systematic search technique that builds a solution incrementally, one choice at a time, and abandons ("backtracks" from) any partial path as…
N-Queens Problem: How Would You Solve It?
The N-Queens problem is solved with backtracking: place queens column by column, and at each row try every column, only proceeding if the position is not attac…
0/1 Knapsack Problem: How Would You Solve It?
The 0/1 knapsack problem is solved with dynamic programming: build a table dp[i][w] representing the best value achievable using the first i items within capac…
Unbounded Knapsack Problem: How Is It Different?
The unbounded knapsack problem allows each item type to be picked an unlimited number of times, so the DP recurrence becomes dp[w] = max(dp[w], value[i] + dp[w…
Coin Change Problem: How Would You Solve It?
The coin change problem (minimum coins to make an amount) is solved with dynamic programming: dp[a] holds the fewest coins needed to make amount a, computed as…
Edit Distance Problem: How Would You Solve It?
Edit distance (Levenshtein distance) is solved with dynamic programming: dp[i][j] holds the minimum number of insertions, deletions, and substitutions to turn…
What is the Lowest Common Ancestor (LCA) Problem?
The lowest common ancestor problem asks for the deepest node in a tree that has both of two given nodes as descendants, and it is typically solved in O(n) with…
What are Inorder, Preorder, and Postorder Tree Traversals?
Inorder, preorder, and postorder are the three depth-first orders for visiting a binary tree's nodes, differing only in when the current node is visited relati…
What is the Divide and Conquer Strategy?
Divide and conquer is an algorithm design strategy that breaks a problem into smaller independent subproblems of the same type, solves each subproblem recursiv…
How Do You Reverse a Linked List in Groups of K?
Reversing a linked list in groups of k means walking the list k nodes at a time, reversing the pointers within each full group of k while leaving any trailing…
How Do You Flatten a Multilevel Linked List?
You flatten a multilevel doubly linked list, where nodes can have a child pointer to a separate sublist in addition to next and prev, by depth-first traversal:…
Word Search Problem: How Would You Solve It?
Word search is solved with backtracking DFS: from every cell matching the word's first letter, recursively explore the four orthogonal neighbors while the next…
What is the Flood Fill Algorithm?
Flood fill is a traversal algorithm that starts at a given cell in a grid and recursively or iteratively spreads to all orthogonally (or optionally diagonally)…
How Do You Detect a Cycle in a Directed Graph?
You detect a cycle in a directed graph with DFS that tracks each node's state as unvisited, in the current recursion path, or fully processed — a cycle exists…
How Does Matrix Chain Multiplication Work?
Matrix chain multiplication finds the cheapest order to parenthesize a chain of matrix multiplications — not the product itself — using dynamic programming in…
What is the Rod Cutting Problem?
The rod cutting problem asks for the maximum revenue obtainable by cutting a rod of length n into pieces and selling each piece at a given price, and it is sol…
What is the Egg Drop Problem?
The egg drop problem asks for the minimum number of trial drops needed, in the worst case, to find the exact floor in an n-floor building at which eggs start b…
What is the Boolean Parenthesization Problem?
The boolean parenthesization problem counts, given a string of boolean operands (T/F) separated by operators (AND, OR, XOR), how many ways parentheses can be i…
What are Catalan Numbers and Their Applications?
Catalan numbers are a sequence C(n) = (2n choose n) / (n+1), computed recursively as the sum over i from 0 to n-1 of C(i)*C(n-1-i), and they count a surprising…
How Do You Solve Fibonacci with Dynamic Programming?
Naive recursive Fibonacci recomputes the same subproblems exponentially many times, costing O(2^n) time, so dynamic programming fixes this by storing each F(i)…
Showing 24 of 37.