Decomposition Without the Stack Perspective: Understanding Recursion Through Function Cloning

zhu le — Wed, 22 Jan 2025 04:51:13 +0000

For beginners in programming, recursion is often a stumbling block. At first glance, it's like viewing flowers through a fog, and even upon second glance, it remains unclear. Today, I will use a visual approach to break down and thoroughly explain recursion, helping you fully grasp its essence.

In one sentence: recursion is when a function calls itself. Since in the real world, a person cannot lift themselves up, it's initially difficult to understand the concept of calling itself. So, let's remove this concept and focus solely on the idea of function calls.

When introducing recursion, the most common example is calculating the nth value in the Fibonacci sequence. The characteristics of this sequence are that the zeroth value (in coding, we usually start from zero) is fixed at 0, the first value is fixed at 1, and starting from the second term, each term's value is the sum of the two preceding terms.

A simple code implementation looks like this:

When we call fibonacci(0), since 0 <= 1, the function directly returns 0.
When we call fibonacci(1), since 1 <= 1, the function directly returns 1.
Thus, we obtain the values of the first two terms.

However, when we call fibonacci(2), things start to get a bit different. Since 2 > 1, the if condition is skipped, and we reach the dreaded recursive line, which not only contains one recursion but two!

No worries, we can simply remove them, like this:

I imagine some students might be completely baffled by this code:

Don't worry, let me explain what's happening. First, look at the bottom function, still named fibonacci. The difference is that the line that previously called itself twice has been replaced with calls to two other functions, fibonacci1 and fibonacci2. These two new functions are identical to the original fibonacci function; I simply copied the original function with ctrl + c, ctrl + v, and renamed them.

After this modification, we find that the recursion in the fibonacci function has disappeared. It no longer calls itself but calls other functions, which happen to have the exact same functionality as itself. >_<

If you run this modified version, you'll find that it functions exactly the same as the original recursive version and correctly calculates the desired values.

Sharp-eyed students might immediately notice that while fibonacci no longer contains code that calls itself, fibonacci1 and fibonacci2 still do. The recursion hasn't been entirely removed. Yes, that's true, but it's okay because when we call fibonacci(2), you'll see that during execution, the lines inside fibonacci1 and fibonacci2 that call themselves are never actually executed. They are there but never truly participate.

Let's go step by step to see what exactly happens:
Step 1:
Call fibonacci(2)
Step 2:
Enter the fibonacci function, where n = 2

Step 3:
Start the if judgment. Since 2 <= 1 is false, skip the if.

Step 4:
Execute the line fibonacci1(n - 1) + fibonacci2(n - 2). First, execute the left side of the plus sign, i.e., call fibonacci1(n - 1). Here, n = 2, so we're actually calling fibonacci1(1).

But don't forget, there's still code on the right side of the plus sign. After we finish calling fibonacci1(1), we'll return here to call fibonacci2(n - 2). Since n = 2, we'll actually call fibonacci2(0). Yes, no matter what happens inside fibonacci1, it won't affect the value of n. On this line, here, when calling fibonacci1, n = 2, and when calling fibonacci2, n is still 2.

Step 5:
Enter the fibonacci1 function, where n = 1

Step 6:
Start the if judgment. Since 1 <= 1 is true, enter the if and directly return the value of n, which is 1.

Step 7:
Since fibonacci1 has finished executing, proceed to execute the right side of the plus sign, i.e., fibonacci2(n - 2). Remember, we're back here, and n = 2, so we're actually calling fibonacci2(0).

Step 8:
Enter fibonacci2, where n = 0

Step 9:
Start the if judgment. Since 0 <= 1 is true, enter the if and directly return the value of n, which is 0.

Step 10:
We're back to the starting point, inside the fibonacci function. Now, both functions on the left and right sides of the plus sign have been executed. The left side's result is 1, and the right side's result is 0. Therefore, we perform the addition.

According to advanced mathematics, we calculate:
0 + 1 = 1

So, the result of this step is 1, meaning the fibonacci function ultimately returns 1.

Finally, we assign the returned result to result.

At this point, we've completed the calculation of fibonacci(2) and obtained the desired result, all without using recursion.

So, what is recursion? Let's return to the concept of recursion and restore the code to its original form:

Then, let's execute it again and see the final result:

Look closely, look closely.
We find that, apart from the function names, the original version and our modified non-recursive version are identical in every way. Their calling methods, the values of n inside the functions, and their returned results are all the same.

Think carefully, think carefully.
Have you realized that recursion is simply calling a function, but it just so happens that the function it calls is itself? We can imagine it as calling another function that has the exact same functionality as itself, and this function happens to have the same name.

Termination Condition
Due to the peculiarity of calling itself, you can imagine a cat chasing its own tail. Therefore, compared to functions that don't call themselves, we need to pay special attention to one thing when using recursion: the termination condition.
Just as a cat chasing its tail will eventually stop—perhaps because it's tired or distracted by a more interesting ball of yarn—without these, the cat might chase its tail forever.
When using recursion, it's especially important to focus on the termination condition; otherwise, the calls will continue indefinitely, eventually leading to a stack overflow.

Taking the fibonacci function as an example, we can see that where it calls itself, the parameters are n - 1 and n - 2, both of which are smaller than n. In the if condition, our judgment is if (n <= 1). Therefore, as the calls continue, n will get smaller and smaller, and eventually, n will be less than or equal to 1. At this point, we enter the if block, where we no longer call itself, and the infinite process is terminated.

I hope this helps!

Introducing Our Python&JavaScript Code Visualization Tool: Revolutionizing Code Understanding

zhu le — Sun, 12 Jan 2025 05:56:04 +0000

Hey everyone!

I’m excited to share a project I’ve been working on that I believe can be a game-changer for developers, educators, and anyone passionate about understanding the inner workings of algorithms and data structures.

What is it?

Our Data Structure & Algorithm Visualization Tool is an interactive platform designed to help you visualize and understand complex data structures and algorithms in a way that’s both intuitive and engaging. Whether you're a seasoned developer or just starting out, this tool provides a dynamic environment to explore how different algorithms manipulate data structures.

Key Features

1. Interactive Visualizations

Real-time Updates: Watch as your code executes and see how data structures change with each operation.
Step-by-step Playback: Control the visualization speed and step through operations.
Highlighted State Changes: Clear visual indicators show exactly what’s changing at each step.
Intuitive Representations: Each data structure has a carefully designed visual representation.

2. Supported Data Structures

Linear Data Structures:
- Arrays: 1D and 2D arrays with element-level visualization.
- Linked Lists: Visual node connections and pointer movements.
- Stacks: Vertical visualization with clear LIFO operations and push/pop animations.
- Queues: Horizontal visualization with FIFO operations and enqueue/dequeue animations.
Tree Structures:
- Binary Trees: Node-link diagrams with clear parent-child relationships and support for traversal visualization.
- Hashmaps: Key-value pair visualization.

3. Code Integration

Language Support: Currently supports JavaScript and Python, with more languages on the horizon.

4. Helper Functions

We’ve provided a set of helper functions to create and convert data structures, making it easier to integrate your code with the visualization tool. Check out the helper functions documentation for more details.

5. Annotations and Customization

Use special annotations to customize how your code is visualized. For example, the @ignore-function-tree annotation can be used to prevent the visualizer from drawing function call nodes in the visualization tree. Learn more about available annotations in the annotations config.

6. Code Transition Feature

Click on code elements to automatically transition to the relevant execution step. This feature is particularly useful for understanding loop iterations, conditional branches, and variable state changes. Read more about it in the code transition guide.

How It Helps Developers

Enhanced Understanding: Gain a deeper understanding of how algorithms work by visualizing their execution.
Debugging Made Easy: Identify issues in your code by watching how data structures change over time.
Educational Tool: Perfect for teaching complex concepts to students or team members.

Examples and Use Cases

Check out our examples page to see the tool in action with various data structures and algorithms. From simple arrays to complex binary trees, we’ve got you covered.

Getting Started

Ready to dive in? Visit our getting started guide to learn how to use the tool and start visualizing your code today!

Future Enhancements

We’re continuously working on improving the tool. Some of the upcoming features include:

Additional data structure support
More annotation types
Enhanced visualization controls
Custom visualization themes
Export/share capabilities

Conclusion

I’m thrilled to share this tool with the community and can’t wait to see how it helps you in your coding adventures. Whether you’re building the next big thing or just trying to understand how algorithms work, this tool is here to make your journey smoother and more enjoyable.

Let’s build a better understanding of code, one visualization at a time!

DEV Community: zhu le