Calling yourself over and over, but getting simpler with each call—that’s recursion in a nutshell! It’s an informal definition, but it captures the essence perfectly.
While the natural follow-up to my last article on Sliding Window would be the Two-Pointer pattern, we’re taking a little detour. Why? Sometimes, tackling concepts that are a bit different can actually make learning easier:
1) It gives the brain some variety to work with.
2) Let’s face it, there’s only so much array manipulation we can take before things start to blur together!
Plus, recursion is a must-know before diving into binary trees, so this article will focus on that. Don’t worry—Two-Pointer pattern and tree introductions are coming soon. We’re just making a strategic stop to keep things fresh!
Recursion 101
Recursion is one of those concepts where building intuition matters more than memorizing definitions. The key idea? Repetition and making the problem progressively simpler.
So, what is recursion?
Recursion is about repeating a process over and over again on a problem, but with each repetition, the problem becomes simpler until you hit a point where it can’t be simplified anymore—this is called the base case.
Let’s break it down with some basic rules.
Rule 1: The problem must get smaller
On each iteration, the problem should reduce in size or complexity. Imagine starting with a square, and with each step, you shrink it.
Note: If, instead of a smaller square, you get random shapes, it’s no longer a recursive process, the simpler problem is the smaller version of the larger one.
Rule 2: There must be a base case
A base case is the simplest, most trivial version of the problem—the point where no further recursion is needed. Without this, the function would keep calling itself forever, causing a stack overflow.
Example: Counting down
Let’s say you have a simple problem: counting down from x to 0. This isn’t a real-world problem, but it’s a good illustration of recursion.
function count(x) { // Base case if (x == 0) { return 0; } // Recursive call: we simplify the problem by reducing x by 1 count(x - 1); // will only run during the bubbling up // the first function call to run is the one before base case backwards // The printing will start from 1.... console.log(x) }
In this example, calling count(10) will trigger a series of recursive calls, each one simplifying the problem by subtracting 1 until it reaches the base case of 0. Once the base case is hit, the function stops calling itself and the recursion "bubbles up," meaning each previous call finishes executing in reverse order.
Recursive Tree Example
Here's an ASCII representation of how recursive calls work with count(3):
count(3) | +-- count(2) | +-- count(1) | +-- count(0) (base case: stop here)
Anything returned from count(0) will "bubble" up to count(1) ... up to count 3.
So it compounds from the most trivial base case!.
More problems!
Recursive examples
Remember the intuition part? the more recursive problems you solve the better, this is a quick overview of classic recursion problems.
Factorial
The factorial of a number n is the product of all positive integers less than or equal to n.
const factorialRecursive = num => { if(num === 0) { return 1; } return num * factorialRecursive(num - 1); }
visual
factorialRecursive(5)
factorialRecursive(5) │ ├── 5 * factorialRecursive(4) │ │ │ ├── 4 * factorialRecursive(3) │ │ │ │ │ ├── 3 * factorialRecursive(2) │ │ │ │ │ │ │ ├── 2 * factorialRecursive(1) │ │ │ │ │ │ │ │ │ ├── 1 * factorialRecursive(0) │ │ │ │ │ │ │ │ │ │ │ └── returns 1 │ │ │ │ └── returns 1 * 1 = 1 │ │ │ └── returns 2 * 1 = 2 │ │ └── returns 3 * 2 = 6 │ └── returns 4 * 6 = 24 └── returns 5 * 24 = 120
Notice how the previous computed answer bubbles up, the answer of 2 * factorialRecursive(1) bubbles up to be an arg for 3 * factorialRecursive(2) and so on...
fibonnaci
A recursive function that returns the nth number in the Fibonacci sequence, where each number is the sum of the two preceding ones, starting from 0 and 1.
const fibonacci = num => { if (num <p>Visual</p> <p>fibonacci(4)<br> </p> <pre class="brush:php;toolbar:false">fibonacci(4) │ ├── fibonacci(3) │ ├── fibonacci(2) │ │ ├── fibonacci(1) (returns 1) │ │ └── fibonacci(0) (returns 0) │ └── returns 1 + 0 = 1 │ ├── fibonacci(2) │ ├── fibonacci(1) (returns 1) │ └── fibonacci(0) (returns 0) └── returns 1 + 1 = 2 a bit tricky to visualize in ascii (way better in a tree like structure)
This is how it works:
- fibonacci(4) calls fibonacci(3) and fibonacci(2).
-
fibonacci(3) breaks down into:
- fibonacci(2) → This splits into fibonacci(1) (returns 1) and fibonacci(0) (returns 0). Their sum is 1 + 0 = 1.
- fibonacci(1) → This returns 1.
- So, fibonacci(3) returns 1 (from fibonacci(2)) + 1 (from fibonacci(1)) = 2.
-
fibonacci(2) breaks down again:
- fibonacci(1) returns 1.
- fibonacci(0) returns 0.
- Their sum is 1 + 0 = 1.
- Finally, fibonacci(4) returns 2 (from fibonacci(3)) + 1 (from fibonacci(2)) = 3.
Optimization challenge: If you notice in the viz, fib(2) is calculated twice its the same answer, can we do something? cache? imagine a large problem with duplicates!
Sum Array
Write a recursive function to find the sum of all elements in an array.
const sumArray = arr => { if(arr.length == 0){ return 0 } return arr.pop() + sumArray(arr) }
visual
sumArray([1, 2, 3, 4])
sumArray([1, 2, 3, 4]) │ ├── 4 + sumArray([1, 2, 3]) │ │ │ ├── 3 + sumArray([1, 2]) │ │ │ │ │ ├── 2 + sumArray([1]) │ │ │ │ │ │ │ ├── 1 + sumArray([]) │ │ │ │ │ │ │ │ │ └── returns 0 │ │ │ └── returns 1 + 0 = 1 │ │ └── returns 2 + 1 = 3 │ └── returns 3 + 3 = 6 └── returns 4 + 6 = 10
This covers the basics, the more problems you solve the better when it comes to recursion.
I am going to leave a few challenges below:
Challenges for Practice
- Check Palindrome: Write a recursive function to check if a given string is a palindrome (reads the same backward as forward).
console.log(isPalindrome("racecar")); // Expected output: true console.log(isPalindrome("hello")); // Expected output: false
- Reverse String: Write a recursive function to reverse a given string.
console.log(reverseString("hello")); // Expected output: "olleh" console.log(reverseString("world")); // Expected output: "dlrow"
- Check Sorted Array: Write a recursive function to check if a given array of numbers is sorted in ascending order.
console.log(isSorted([1, 2, 3, 4])); // Expected output: true console.log(isSorted([1, 3, 2, 4])); // Expected output: false
Recursion is all about practice and building that muscle memory. The more you solve, the more intuitive it becomes. Keep challenging yourself with new problems!
If you want more exclusive content, you can follow me on Twitter or Ko-fi I'll be posting some extra stuff there!
The above is the detailed content of Interview Kit: Recursion.. For more information, please follow other related articles on the PHP Chinese website!

JavaScript runs in browsers and Node.js environments and relies on the JavaScript engine to parse and execute code. 1) Generate abstract syntax tree (AST) in the parsing stage; 2) convert AST into bytecode or machine code in the compilation stage; 3) execute the compiled code in the execution stage.

The future trends of Python and JavaScript include: 1. Python will consolidate its position in the fields of scientific computing and AI, 2. JavaScript will promote the development of web technology, 3. Cross-platform development will become a hot topic, and 4. Performance optimization will be the focus. Both will continue to expand application scenarios in their respective fields and make more breakthroughs in performance.

Both Python and JavaScript's choices in development environments are important. 1) Python's development environment includes PyCharm, JupyterNotebook and Anaconda, which are suitable for data science and rapid prototyping. 2) The development environment of JavaScript includes Node.js, VSCode and Webpack, which are suitable for front-end and back-end development. Choosing the right tools according to project needs can improve development efficiency and project success rate.

Yes, the engine core of JavaScript is written in C. 1) The C language provides efficient performance and underlying control, which is suitable for the development of JavaScript engine. 2) Taking the V8 engine as an example, its core is written in C, combining the efficiency and object-oriented characteristics of C. 3) The working principle of the JavaScript engine includes parsing, compiling and execution, and the C language plays a key role in these processes.

JavaScript is at the heart of modern websites because it enhances the interactivity and dynamicity of web pages. 1) It allows to change content without refreshing the page, 2) manipulate web pages through DOMAPI, 3) support complex interactive effects such as animation and drag-and-drop, 4) optimize performance and best practices to improve user experience.

C and JavaScript achieve interoperability through WebAssembly. 1) C code is compiled into WebAssembly module and introduced into JavaScript environment to enhance computing power. 2) In game development, C handles physics engines and graphics rendering, and JavaScript is responsible for game logic and user interface.

JavaScript is widely used in websites, mobile applications, desktop applications and server-side programming. 1) In website development, JavaScript operates DOM together with HTML and CSS to achieve dynamic effects and supports frameworks such as jQuery and React. 2) Through ReactNative and Ionic, JavaScript is used to develop cross-platform mobile applications. 3) The Electron framework enables JavaScript to build desktop applications. 4) Node.js allows JavaScript to run on the server side and supports high concurrent requests.

Python is more suitable for data science and automation, while JavaScript is more suitable for front-end and full-stack development. 1. Python performs well in data science and machine learning, using libraries such as NumPy and Pandas for data processing and modeling. 2. Python is concise and efficient in automation and scripting. 3. JavaScript is indispensable in front-end development and is used to build dynamic web pages and single-page applications. 4. JavaScript plays a role in back-end development through Node.js and supports full-stack development.


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Safe Exam Browser
Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

Zend Studio 13.0.1
Powerful PHP integrated development environment

mPDF
mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

SublimeText3 Chinese version
Chinese version, very easy to use

Atom editor mac version download
The most popular open source editor
