Recursion — Simple English

35 lessons · Data Structures & Algorithms · Simple English · Beginner Friendly

01 How a Program Lives in Memory: From Source Code to Running ProcessFree How a Program Lives in Memory Before we learn recursion, we need a clear picture of what really happens when a program r… 02 How Source Code Becomes a Running Program: The Compilation PipelineFree How Source Code Becomes a Running Program When you write a program in a language like C or C++, you type words and symbo… 03 How an Interpreter Runs Your Code: From Source Text to ActionFree How an Interpreter Runs Your Code When you write a program, the computer cannot understand your text directly. The words… 04 How a Program's Memory Is Organized: Heap, Stack, Static, and Code🔒 How a Program's Memory Is Organized When you run a program, the computer turns it into a process — a running copy of you… 05 Understanding the Stack Frame: How Function Calls Work in Memory🔒 Understanding the Stack Frame When a program runs a function, the computer needs a tidy place to keep all the details th… 06 How Nested Function Calls Use the Stack🔒 How Nested Function Calls Use the Stack Real programs are almost never just one function. They are built from many small… 07 Stack Overflow: When the Call Stack Runs Out of Room🔒 Stack Overflow: When the Call Stack Runs Out of Room Every time your program calls a function, the computer sets aside a… 08 Understanding the Problem: What Recursion Really Is🔒 What Is Recursion? You already know how a program keeps track of function calls using memory and stack frames. Now we ar… 09 The Queue Trick: Finding Your Position with Recursion🔒 The Queue Trick: Finding Your Position with Recursion Imagine you are standing in a long line at an ATM. You want to kno… 10 The Key Parts of Recursion: Recursive Structure, Base Case, Recursive Relation, and the Recursion Tree🔒 The Key Parts of Recursion You already have a rough idea of how recursion works — a problem that solves itself by callin… 11 How Recursion Really Works: Function Calls, the Base Case, and Stack Unwinding🔒 How Recursion Runs Step by Step Recursion is just a function calling itself. That sounds strange at first, but it works … 12 Head Recursion: Building the Answer from the Bottom Up🔒 Head Recursion: Building the Answer from the Bottom Up A recursive function is a function that calls itself to solve a s… 13 Head Recursion: Solve the Small Problem First, Then Combine🔒 Head Recursion Recursion is when a function calls itself to solve a smaller version of the same problem. Head recursion … 14 Building the Forward Sequence 1 to N Using Recursion🔒 Building the Forward Sequence 1 to N Using Recursion Imagine someone gives you a number, say 5, and asks you to make a l… 15 Calculating Factorial Using Recursion🔒 Calculating the Factorial of a Number What is a factorial? The factorial of a number is what you get when you multiply t… 16 Sum of Digits (Using Recursion)🔒 Sum of Digits Using Recursion Let's solve a simple but very useful problem. We are given a whole number that is zero or … 17 Reversing a Queue Using Recursion🔒 Reversing a Queue Using Recursion A queue is a line of items where you can only add to the back and remove from the fron… 18 Tail Recursion: Building the Answer Top-to-Bottom🔒 Tail Recursion Tail recursion is the exact opposite of head recursion. In a tail-recursive function, the function calls … 19 Tail Recursion: Solving Problems with Loop-Like Recursion🔒 Tail Recursion Recursion just means a function that calls itself to solve a smaller version of the same problem. Tail re… 20 Building a Reverse Sequence with Recursion🔒 Building a Reverse Sequence with Recursion Here is the task we want to solve. You are given a positive whole number N. Y… 21 Search for an Element in an Array Using Recursion🔒 Searching for an Element in an Array One of the most basic things we do with data is look for something inside it. Imagi… 22 Check if an Array is a Palindrome (Using Recursion)🔒 Check if an Array is a Palindrome What does "palindrome" mean? A palindrome is something that reads the same forwards an… 23 Reversing a Singly Linked List Using Recursion🔒 Reversing a Singly Linked List Using Recursion Imagine a chain of train cars. Each car holds a value and is connected to… 24 Multiple Recursion: When a Function Calls Itself Many Times🔒 Multiple Recursion What "recursion" means first Recursion is when a function solves a problem by calling itself on a sma… 25 Multiple Recursion: Solving Problems by Combining Many Subproblems🔒 Multiple Recursion So far you may have seen recursion where a function calls itself just once for a smaller version of t… 26 Finding the Nth Fibonacci Number Using Recursion🔒 The Fibonacci Number Problem The Fibonacci sequence is one of the most famous number patterns in all of programming. The… 27 The Zigzag Sequence: Building Numbers from the Three Before Them🔒 The Zigzag Sequence Some sequences of numbers follow a simple pattern, like 2, 4, 6, 8 (keep adding 2). The zigzag seque… 28 Climbing Stairs: Counting Ways with Recursion🔒 Climbing Stairs: How Many Ways to the Top? Imagine a staircase with N steps. You want to reach the very top. But there i… 29 Catalan Numbers: Counting with Recursion🔒 Catalan Numbers Some counting problems pop up again and again in computer science and math. When you count things like "… 30 Multidimensional Recursion: Solving Problems That Branch Across Many Dimensions🔒 Multidimensional Recursion What "dimension" really means here In ordinary recursion, you usually shrink one number with … 31 Multidimensional Recursion: Solving Problems with Many Variables (with N choose K)🔒 Multidimensional Recursion Recursion is when a function calls itself to solve a smaller version of the same problem. So … 32 Binomial Coefficient: Counting How Many Ways to Choose🔒 Binomial Coefficient: Counting Ways to Choose Imagine you have a basket of 5 different fruits, and you want to pick 3 of… 33 Lattice Paths: Counting Routes Through a Grid with Recursion🔒 Lattice Paths: Counting Routes with Recursion Imagine you are standing at the top-left corner of a grid, and you want to… 34 The Ackermann Function: A Deeply Recursive Problem🔒 The Ackermann Function Most functions you write call themselves a few times and then stop. The Ackermann function is spe… 35 The Egg Dropping Problem: Fewest Tries in the Worst Case🔒 The Egg Dropping Problem Imagine you are standing in a building, holding some eggs. There is one special floor in this b…