Michael has a diverse background in software engineering, mechanical engineering, economics, and management. After a successful career in mechanical engineering, Michael decided to become a software engineer and attended the Hack Reactor coding bootcamp. Michael enjoys writing about his experiences and helping others start their journies in software development.
Recursion is a programming technique where a function calls itself to solve a particular problem. It’s especially effective for problems that can be divided into smaller, similar subproblems. By breaking down a complex problem in this way, recursion can often lead to elegant and concise solutions.
A recursive function repeatedly calls itself with smaller versions of the problem until it reaches a simple, solvable base case. This self-referential approach is a powerful tool for tackling problems that have a recursive structure.
While the concept can be challenging to grasp, recursion can be likened to solving a jigsaw puzzle. Some puzzle solvers might start by connecting a few pieces together that have similar colors, and they might do so until they have a few groupings of puzzle pieces. They might then connect those groupings into one larger grouping. This strategy can go on until the entire puzzle is completed.
Recursion Fundamentals
For some, it can be easier to learn by reading code, but before we can demonstrate recursion by programming out an example, we need to explain some fundamental concepts of recursion.
In recursion, “cases” are the different scenarios that dictate how a recursive function behaves. These cases logically guide the function on whether to continue recursing or to terminate. Correctly identifying and implementing these cases is essential to ensuring that a recursive function works as intended and doesn’t fall into an infinite loop.
There are typically two primary cases in recursion: the base case and the recursive case.
Base Case
The base case is the condition under which the recursive function stops calling itself. It is the simplest instance of the problem that can be solved directly without further recursion, and it is critical because it prevents infinite recursion by providing a stopping point. The base case stops the recursion when the problem has been reduced to its simplest form or has reached the end of the sequence.
Recursive Case
The recursive case is the condition under which the function continues to call itself with modified arguments. In these scenarios, the function makes progress towards the base case by simplifying or reducing the problem with each recursive call. The recursive case helps to break the problem into smaller sub-problems that have the same structure as the original problem, but with simpler or reduced inputs.
Recursion in JavaScript
Let’s recreate the Math.pow method, which calculates the power of a number, using recursion in JavaScript. The Math.pow(base, exponent) function computes the result of raising thebase value to the power of an exponent.
Recursive Math.pow Implementation
To implement this method using recursion, we’ll use two main cases:
Base Case: If the exponent is 0, the result is 1 because any number raised to the power of 0 is 1.
Recursive Case: Multiply the base by the result of the function with the exponent decremented by 1.
Here’s the JavaScript implementation:
function recursivePow(base, exponent) {
if (exponent === 0) {
return 1;
} else if (exponent < 0) {
return 1 / recursivePow(base, -exponent);
} else {
return base * recursivePow(base, exponent - 1);
}
}
Explanation of the Code
Base Case: If the exponent is 0, the function returns 1. This stops the recursion from continuing indefinitely.
Edge Case: If the exponent is negative, the function inverts the base (i.e. calculates 1 / base) and calls itself with the positive value of the exponent. This allows the function to correctly compute the result for negative exponents.
Recursive Case: If the exponent is positive and greater than 0, the function multiplies the base by the result of calling itself with the exponent decremented by 1. The decrementing by one is critical because this causes the recursive calls to home in on base case (i.e. reducing the exponent by 1 until it reaches 0).
How the Recursion Unfolds
A flow diagram visualizing a recursive implementation of Math.pow
Let’s walk through an example where we invoke the recursive power function with a base of 2 and a power of 3 (recursivePow(2, 3)). Note, in the illustration above, I’ve omitted the edge case logic for visual clarity.
recursivePow(2, 3) returns 2 * recursivePow(2, 2)
recursivePow(2, 2) returns 2 * recursivePow(2, 1)
recursivePow(2, 1) returns 2 * recursivePow(2, 0)
recursivePow(2, 0) returns 1 (base case)
As the call stack unwinds and the function invocations return their values, the result is equivalent to: 2 * 2 * 2 * 1 = 8.
This implementation of Math.pow using recursion is a great way to illustrate the power of recursion by breaking down problems into smaller sub-problems, solving them recursively, and combining the results to obtain the final solution.
The Pros and Cons of Using Recursion
Pros of Using Recursion
Optimal Technique: For problems that involve manipulating or iterating through dynamic data structures—such as traversing through a tree or linked list—or while designing solutions that involve sorting or using a divide-and-conquer strategy, recursion naturally lends itself to elegant implementations in these scenarios.
Brevity: Recursion can often require fewer lines of code compared to their equivalent iterative solutions, which can make the codebase less verbose and cleaner.
Cons of Using Recursion
Performance Overhead: Recursion can be less memory-efficient than iterative solutions due to the overhead of multiple function calls. Each recursive call adds a new frame to the call stack, which can lead to excessive memory usage and a higher space complexity.
Risk of Stack Overflow: Anyone first learning about recursion has probably caused a stack overflow. If the recursion depth becomes too deep, it can lead to a stack overflow error, especially in languages with limited stack size. This happens when there are too many nested function calls before reaching the base case. While tail call optimization —where the recursive case is in the tail position and therefore could optimized to not grow the call stack—few JavaScript engines have implemented support for this ECMAScript 6 feature.
Debugging Difficulty: Recursive functions can be harder to debug and trace, especially if the base case is not correctly defined, leading to infinite recursion.
When to Use Recursion
Recursion is particularly useful when dealing with problems that have a natural recursive structure, such as:
Tree Traversal: Traversing hierarchical data structures like binary trees or graphs is more intuitive with recursion.
Divide and Conquer Algorithms: Algorithms like QuickSort and MergeSort benefit from recursion as they divide the problem into smaller subproblems.
Dynamic Programming: Some dynamic programming problems, such as calculating Fibonacci numbers, can be solved using recursion (though they may require memoization to optimize performance).
Conclusion
Recursion is a powerful tool in a programmer’s toolkit that allows for elegant and concise solutions to complex problems. However, it’s essential to understand when and how to use recursion effectively, considering both its advantages and potential pitfalls. By carefully structuring recursive functions and being mindful of base cases and stack depth, you can harness the full potential of recursion in your software projects.
I was working in the hard disk drive industry as a Senior Research and Development Engineer when I knew that I wanted to work on software. I had a degree in Mechanical Engineering and an established career with six years of experience, but the idea of switching careers this late in the game was daunting. Could I really handle going back to school? Is it a bad idea to leave my old career behind and start again from the beginning? These are questions that were racing through my head as I was trying to figure out my future.
I decided to make the switch, but it wasn’t easy. Big life decisions require lots of thought and research, but they also require you to follow your heart. My background in engineering prepared me for problems of this magnitude. I had learned over the years that the best way to tackle a large project or problem is to break it down into its components. And if possible, make these components independent of each other so that you can work on them separately.
So I decided to split up my large, daunting decision into two smaller, manageable decisions. I needed to figure out what it is that I wanted, and only then figure out how I was going to get there. I wanted to make a career out of working on software projects I cared about. So once I decided that’s what I was going to do, a huge weight was lifted off of my shoulders. I was now energized to figure out how I was going to reach that goal.
Fast forward to now, I’m a Senior Software Engineer with about 5 years of experience under my belt. At the time, my journey to becoming a software engineer by attending a coding bootcamp was very new and uncommon. Today, it’s a much more popular route, and so I’d like to share a few things I learned along the way.
1. Bootcamps can help you learn what you’re capable of
Throughout my life, I’ve always pushed myself to work hard and achieve my goals. I graduated with honors in three years with my Mechanical Engineering degree. I started an apparel printing small business for fun while in grad school. I successfully flipped a property with no prior experience in carpentry or real estate. But completing the Hack Reactor bootcamp may have been the most challenging of them all.
On average, I was in class or studying for 12 to 14 hours per day, 6 days per week, for 3 months straight. Every 2 days we learned about a new technology and how to use it. It was mentally and physically exhausting, while also testing you emotionally. Being away from your friends, family, and normal life for 3 months is no joke. Even if you’re doing a full remote bootcamp, you have almost no free time.
Bootcamps put you under somewhat artificial pressure by using aggressive deadlines and pushing lofty goals. This pressure will make or break you. I’ve seen a few people fold under the pressure, but for the most part, students are generally able to rise to the challenge and come out well-equipped to handle anything.
Not everyone is meant to be a software engineer, and I think that needs to be said. While I think that given enough time and resources everyone can learn to code, that doesn’t mean that everyone should. Being a software engineer means shifting your mindset to programmatic thinking. If that’s a big, unnatural shift for you, you’re probably not going to have a smooth career trajectory.
Even more so, not everyone is going to be able to successfully complete and thrive in a coding bootcamp. This is because as I mentioned before, bootcamps are physically, mentally, and emotionally demanding. This type of fast-paced, rapidly changing environment can be difficult in general, not just for people trying to break into software development. Some current software engineers wouldn’t thrive in this type of scenario, and similarly, if this format were applied to a different profession, I think it would also prove to be challenging for many.
The inherent complexity of software engineering curriculum combined with the strenuous nature of the bootcamp format produces an entirely new dimension of education difficulty. It’s not for everyone, but for whom it does appeal to, it can easily be the best option to crack into software development.
3. Bootcamps don’t really teach you much and that’s okay
Syllabi vary from bootcamp to bootcamp, but to become a passable software engineer, you have to code. A lot. You have to code all day, every day. That’s one thing that all bootcamps have in common: they know how much you need to code. That doesn’t leave a lot of time for lecturing, one-on-one tutoring, or much of anything else.
Hack Reactor was structured with 2-day “sprints” for the first half of the bootcamp. For the most part, the beginning of each sprint began with a short lecture where a new technology or concept was introduced. The rest was coding. And these introductions weren’t deep dives, they were just enough to get you going or to point you in the right direction. The value of the bootcamp isn’t in its lecture time or its world-renowned staff. The primary value is derived from two different sources: the brand name and the power to produce autonomous engineers.
At first, the brand name didn’t mean much. Without a Computer Science (CS) degree, you were going to have a difficult time getting an interview anywhere. As bootcamps kept producing quality engineers, the brand name became another layer of authentication. Now employers know if you graduate from Hack Reactor, you’ve been put through the wringer.
Bootcamps can help you become autonomous. Along the journey you’ll get stuck, you’ll feel lost or burnt out, and you’ll likely get a heavy dose of impostor syndrome. But with small nudges in the right direction, you’ll realize the answer is always in the code, you’ll be able to Google your way out of dead-ends, and you’ll start to use computer science principles to write better code. At the end of the bootcamp, you’ll start to understand that given enough time and resources, you can learn anything.
4. Imposter Syndrome is real and never really goes away
Most people will experience imposter syndrome at some point in their lives. There will always be someone smarter or who knows the subject matter better than you, and it will make you feel like an imposter. Bootcamps are no exception. In fact, they are little imposter syndrome factories.
The nature of a bootcamp is to move fast and figure things out as you go. So you’re essentially guaranteed to feel uncomfortable, and that’s by design. There is always something else to learn, and the assignments always have stretch goals for you to take on if you finish early. Bootcamps help you become comfortable with being uncomfortable.
So when you land your first job and all of the engineers around you know more than you, you feel like an impostor. But you don’t sweat it because you’ve been there before and you can handle much more than being a little uncomfortable. Imposter syndrome doesn’t go away, it just changes its appearance.
5. New software technologies emerge often and curriculum needs to adapt to keep up
Getting a traditional university Computer Science degree is a great way to land a software engineering job. They help you build a strong technical foundation from the ground up, and the prestige associated with several of the programs out there will give you a leg up on the competition.
However, universities move at the speed of universities: slow. To be accredited, colleges have to teach certain curriculum standards and meet other comprehensive requirements. CS programs also don’t typically have a lot of incentive to innovate and reevaluate their standards frequently. They historically only really compete amongst other university programs, and the prestige of a program is often established by its research and famous faculty.
Coding bootcamps operate on a different model. They look to fill the void that traditional CS programs left behind by teaching and stressing technologies that are often only touched upon in elective classes at university. The general CS degree model is to teach fundamentals and use optional elective classes to explore new technologies and trends. Bootcamps invert that model. They stress new technologies and trends and only briefly touch upon fundamentals. This model has proven to be successful because bootcamp graduates:
have proven they can flourish in a stressful environment,
have tons of hands-on experience with in-demand technologies, and
are entering a field that has a rapidly growing demand for their skillset.
When I attended Hack Reactor’s onsite bootcamp in San Francisco, I had no idea you could fail and get kicked out. I knew there was a midterm exam at the halfway point of the course, but I didn’t know the gravity of the situation.
Along the way, I saw some of my classmates burn out from the extreme pace of the program. I saw another get sick, miss one day, and be so far behind that he never caught up and ended up dropping out. I saw another classmate be told that she didn’t have what it took to succeed in interviews, failed after the midterm exam, only to be reinstated after she complained to them about their assessment of her.
Overall, I had a great experience at Hack Reactor, and the program went a long way to set me up for success afterward. However, it was frankly unethical to not emphasize the possibility of failure and expulsion from the program before we accepted our invitations. Hopefully, they’ve changed their process and this is no longer a problem.
Software engineers are often portrayed in mainstream media as introverted lone wolves that exude a quiet genius as they work on cutting-edge systems. While that may be accurate in some cases, that couldn’t be further from the truth for the majority of software engineers. Yes, a disproportionate amount of software engineers might be introverted, but that doesn’t mean they don’t have to effectively communicate. Communication is essential in software engineering, and successful coding bootcamps are acutely aware of this.
The first half of the Hack Reactor program is entirely pair programming, where they take the “driver and navigator” approach. This helps you practice translating your thoughts to speech and also translating someone else’s direction into code. This provides you the opportunity to practice critiquing someone else’s work which can be difficult to do without stepping on toes or hurting egos.
The second half of the Hack Reactor program consists of mostly group projects. You get to establish team member roles, dole out responsibilities, practice an effective version management workflow, and many other aspects of working on a team. There is a big difference between working by yourself on a project and working on a team, and in most professional settings you’ll be working on a team.
Additionally, all along the way, you’re practicing whiteboarding. The practice of simultaneously thinking about how to solve a problem, verbalizing those thoughts, and writing them on a whiteboard feels very unnatural. Hack Reactor provided lots of whiteboarding practice time which not only helped prepare me for interviews but made me a more effective communicator.
8. Outcomes are just as important as learning to code
Don’t get me wrong, it will be nearly impossible to land a software engineering job if you don’t know how to code. But let’s consider the scenario where two programmers land entry-level job offers at similar companies. The first is a very talented programmer but doesn’t know their worth nor is an effective negotiator. The second programmer is an average entry-level developer but has been coached on their worth and compensation negotiation. Now let’s imagine they accept approximately the same compensation package as the other. Would you consider this a success for the talented programmer?
Outcomes are just as important as learning to code. By reframing the goal from “becoming a software engineer” to “becoming an appropriately compensated software engineer”, bootcamps can set you up for long-term success that you didn’t even know you cared about.
Graduating from a coding bootcamp was one of the most validating experiences I’ve had in my lifetime. It took a lot of willpower, and I assumed a lot of risk, but it paid off exactly how I imagined it. However, the bootcamp was just the beginning.
Most bootcamp students are looking to land a job after they graduate. Software engineering interviews are some of the most stressful and comprehensive interviews in the job market today. You’ll likely have algorithm questions, whiteboarding, system design questions, and behavioral interviews just to start. You might have take-home projects, purposefully arbitrary riddle-like questions, and much more. This means that you have to study a lot. Bootcamps often prepare you for these sorts of interviews, but it takes practice to become good at them.
Even after you land a job, you’re likely still an entry-level engineer with zero years of experience and a porous knowledge of computer science fundamentals at best. Your intense journey will continue well into your first year on the job. You’ll need to strengthen your core understanding of well-established programming principles that you only truly understand once you have experience not following them. Concepts like Don’t Repeat Yourself (DRY), Single-Responsibility Principle (SRP), and Single Source of Truth (SSOT) are just a few that don’t really hit home until you’ve seen their benefits take shape firsthand.
Things change once you get a year of experience under your belt. A tidal wave of recruiters will drop upon you like you couldn’t imagine, and lots of doors will open for you. You’ve been battle-tested and are starting to proactively learn and improve your skillset like a more senior engineer. But after all of this, your journey is still ongoing. Software engineers are always learning and keeping up with the latest technologies and trends.
When I first started my journey to become a software engineer, I was very skeptical of coding bootcamps. How could one possibly learn enough from an unaccredited school to become a software engineer in 3 months? How could bootcamp grads compete with candidates who have 4-year computer science degrees? It turns out that the answer to both of those questions is “demand”.
Software is always on the cutting edge and often disrupting the status quo. New technologies and patterns emerge all of the time. Just during my short time on this journey, I’ve already seen the rise of Single-Page Applications, Microservices, Cryptocurrencies, Non-Fungible Tokens (NFTs), and Micro-Frontends just to name a few. The rise in these new technologies means there must also be a proportional rise in demand for people to develop using those technologies. If the demand isn’t being fulfilled by traditional routes, alternative education solutions will arise to fill in that void.
Bootcamps are also a part of a larger trend of moving away from universities and their traditional education models. Universities are expensive, bulky, and generally slow to react to the latest demands. Sure they develop new curriculum and periodically review their standards, but software moves much faster than most other industries. On top of that, universities force you to satisfy several different general education requirements. Maybe these requirements help you become a more well-rounded human being and give you a perspective you might not otherwise achieve in your lifetime. But is it absolutely necessary to become a software engineer? No, it’s not. The more economical solution to meet the growing demand is to train people directly in the areas they need to learn to get a job. This vocational school approach is gaining more popularity as universities continue to become financially out of reach for most people.
Conclusion
Bootcamps can help you transform your career in a way that hasn’t been seen before. They move fast and work along the cutting edge of the software engineering industry. Bootcamps are fueled by the rising demand for software engineers that isn’t being satiated elsewhere. While not for everyone, they can provide a more logical and economical approach to education than you might otherwise be afforded.
If you’re thinking about joining a coding bootcamp and are starting to study, check out some of these tutorials.
Attending a coding bootcamp can be a life-changing experience for those looking to break into the lucrative and ever-growing field of software development. These intensive programs offer a concentrated, hands-on approach to learning the skills necessary to become a proficient programmer. Sometimes, in a matter of months, students can acquire the knowledge and expertise to land entry-level or even mid-level positions at tech companies. The curriculum typically covers a wide range of frameworks and tools, enabling graduates to hit the ground running and meaningfully contribute to software development teams.
However, the decision to enroll in a coding bootcamp is not without its challenges. One of the primary concerns for many prospective students is the financial aspect. Bootcamps can be expensive, and the upfront cost can be a significant barrier for those with limited financial resources. Additionally, the accelerated pace of the program can be demanding, requiring a high level of commitment and almost certainly leaving one’s current job. It’s important for individuals to carefully consider their financial situation and personal readiness before making the leap into a coding bootcamp. To help prospective students weigh out their financial situations and the impact of attending a coding bootcamp, we’ve created the Coding Bootcamp Break-Even Calculator.
Break-Even Calculator Definitions
Bootcamp Duration
The duration of a coding bootcamp typically ranges from 12 to 24 weeks. However, this only reflects the core program’s time commitment. There are often pre-course requirements, interviews, and tests, as well as checkpoints, just to be accepted. Some bootcamps are longer, potentially offering more in-depth learning but also delaying entry into the workforce. The course length is a crucial factor in calculating the “break-even” period, as it directly impacts when you can start earning income from a new tech job.
Job Search Duration
The job search duration, or the time spent interviewing and securing a job post-bootcamp, is a significant factor. It can vary widely due to market conditions, individual skills, networking efforts, and economic factors. A prolonged job search delays the start of higher earnings, impacting the time it takes to recoup the bootcamp investment. Anticipating this duration helps set realistic expectations for when you might begin seeing a return on your education investment.
Bootcamp Tuition
Bootcamp tuition is the primary upfront cost of attending a coding bootcamp, typically ranging from $8,000 to $22,000. Some coding bootcamps charge higher tuitions but may also offer enhanced curricula, career support, and overall outcomes. Tuition costs can be a significant factor in choosing a coding bootcamp, but financing options, such as student loans or income share agreements, can help alleviate this burden.
Equipment Costs
Attending a coding bootcamp, especially an online program, requires specific essential items like a laptop and a reliable high-speed internet connection. These costs can vary and should be factored into the total expenses. While some may already have these resources, others may need to invest in them. Accounting for these upfront costs can influence the break-even timeline and should be carefully considered.
Student Loans
When financing a portion of bootcamp tuition with a student loan, consider the loan amount, interest rate, and loan term. These factors determine the total repayment cost, including accrued interest. Understanding these factors helps assess the true cost of borrowing and its impact on the long-term financial benefits of attending a bootcamp. The loan term, or the repayment period, affects monthly payments and the total amount paid. Longer terms reduce monthly payments but increase total interest, potentially affecting the net financial gain. Balancing loan terms with expected future income is crucial for calculating when you’ll break even and start benefiting financially from your bootcamp investment.
Housing Costs
Housing costs, such as rent or mortgage payments, represent a significant ongoing expense during the bootcamp and job search periods. Coding bootcamps, even part-time programs, require significant time investment, making it challenging to succeed while working a full-time job. These costs also accrue during the job search period post-bootcamp. They are important to consider because they affect how much savings you need to cover living expenses during periods of lower or no income.
Food, Transportation, and All Other Expenses
These are additional monthly expenses to be covered during the bootcamp and job search. Lifestyle changes and financial sacrifices are often necessary due to reduced incomes. On the other hand, coding bootcamps can be intensive, which leads to reduced budgets for entertainment, restaurants, and other non-essential items. Accounting for these expenses ensures a realistic understanding of the total costs before earning your new tech salary.
Lost Income
There is an opportunity cost of not working during while attending a coding bootcamp, especially if you would have been earning an income otherwise. This is a critical factor because it directly impacts the total financial loss during the period of education and job search. Often overlooked due to its intangible nature, lost income needs to be accounted for in the break-even analysis, as it represents a significant portion of the overall cost of investing in a bootcamp.
Future Tech-Job Income
One of the primary factors for attending a coding bootcamp is the potential income. While the tech industry offers very high-paying roles, having a realistic picture of your future income is essential for accurate break-even calculations. A higher post-bootcamp income generally means a shorter break-even period, but estimating future income realistically, based on industry standards and job market conditions, is crucial for determining the financial viability of attending a coding bootcamp.
Effective Tax Rates
When calculating the break-even point, it’s essential to use post-tax income, as tuition and other expenses are paid with after-tax funds. Taxes can be complex and progressive, so using an effective tax rate simplifies the calculations. There are many online calculators to estimate effective tax rates for different incomes, but a simple calculation involves dividing the total income taxes paid last year by the total pre-tax income.
In the world of software engineering, understanding different programming paradigms is crucial for writing efficient and maintainable code. One of the most fundamental paradigm decisions to make is the choice between using imperative versus declarative programming. While both approaches can achieve the same outcomes, they do so in fundamentally different ways. We’ll explore the differences between these two patterns, with a focus on JavaScript, and provide examples to illustrate the pros and cons of each.
Imperative vs. Declarative: A Real World Example
Understanding the benefits and drawbacks of these programming concepts is best achieved through hands-on experience. Imagine the challenges of debugging complex, imperatively written code, or the frustration of navigating over-engineered, overly abstract solutions. While these experiences can be invaluable, a real-world analogy can provide a helpful starting point for understanding the differences between imperative and declarative programming.
The first analogy I heard to describe the imperative/declarative relationship was using an automobile’s air conditioner control panel, so let’s explore that in depth.
Imperative Design of an Automobile A/C Control Panel
Description: In the past, some cars’ A/C controls used imperative design, where the user set a fan level, selected a vent, and decided a heating/cooling level.
Usage: Using this system isn’t too complicated, but it requires an understanding of how all three settings work and how different combinations of settings translate to getting the car to the desired temperature. Not only that, but if the weather or conditions change, the user needs to adjust the settings according. If the weather gets colder or hotter, or if the driver takes a weekend trip out of town, those settings might not be appropriate. Heating the car while on a trip to the desert or cooling the car in the cold mornings don’t make much sense.
In other words: The user tells the car how to cool or heat the vehicle.
Declarative Design of an Automobile A/C Control Panel
A Tesla Model 3 Control Panel | Source: Motor Trend
Description: Modern cars, like the Tesla Model 3, have more declarative temperature controls. While the user may dive in and adjust the A/C settings more granularly, the main control is a just a left arrow, a right arrow, and the temperature display.
Usage: By providing controls to adjust the temperature, the user gets to focus on the desired output rather than the underlying mechanics. The user sets the cabin temperature and the car’s sensors and controllers will adjust the underlying settings to maintain the desired output. The user only needs to be concerned about concepts they understand, like comfortable temperatures, and can allow the car to be concerned with vents, fans, and HVAC.
In other words: The user tells the car what temperature they want.
What is Imperative Programming?
As discussed above in the analogy, imperative programming is a paradigm that focuses on how to achieve a particular task. It involves explicitly giving the runtime a sequence of commands or steps to follow in order to reach the desired outcome. In imperative programming, you often define the control flow and manage the state of your program as you go.
What is Declarative Programming?
Declarative programming, on the other hand, focuses on what you want to achieve rather than the intricate details of how to achieve it. In this paradigm, you describe the desired outcome, and the underlying system takes care of the rest. The control flow and state management — the parts of the algorithm that can be made generic and reused elsewhere—are often abstracted away from the algorithm at hand.
An Example of Imperative Programming in JavaScript
Let’s look at a classic example, one that many beginning programmers learn in their early software journeys. Say we want to sum all the numbers in an array. An imperative approach in JavaScript would look like the following:
An example of imperative code written in JavaScript
In the example above, we explicitly define every step of the algorithm:
Initialize a sum variable
Loop through each number in the array
Add each number to the sum
An Example of Declarative Programming in JavaScript
Let’s look at a declarative approach to achieve the same desired output. Using the same example of summing numbers in an array, a declarative approach in JavaScript might use the reduce method on the array prototype:
An example of declarative code written in JavaScript
Here, instead of describing the steps to achieve the sum, we declare that we want to reduce the array to a single value by summing its elements. The reduce method abstracts away the loop and state management.
Pros of Imperative Programming
Control: You have precise control over the flow of your program, which can be useful in complex scenarios where you need to manage the state closely.
Performance: Imperative code can sometimes be optimized for performance, as you can fine-tune every step of the process.
Cons of Imperative Programming
Verbosity: Because you must define each step, imperative code can very quickly become verbose, more difficult to read, and even more difficult to code review. These difficulties compound as complexity increases.
Error-Prone: Managing the state manually can lead to bugs, particularly in complicated programs or when operating in lower-level programming languages.
Testing Difficulty: Writing unit tests can sometimes become, by definition, impossible because concerns are intermixed.
Pros of Declarative Programming
Simplicity: Declarative code is often more concise, easier to understand, and easier to read, as it abstracts away the underlying mechanics.
Maintainability: Because you’re focusing on what you want to achieve, the code is typically easier to maintain and less prone to bugs.
Reviewability: Declarative code can be more readable, especially for those who are familiar with the abstractions used. This can make it much easier for code reviews.
Testability: Writing declarative code often involves separating concerns. This allows for individual features to be isolated and tested easily.
Cons of Declarative Programming
Less Control: You have less control over how the task is executed, which can be a drawback if you need fine-tuned performance optimizations.
Over-Abstraction: The abstractions provided by declarative methods might introduce overhead or may not be suitable for all scenarios, particularly when performance is critical.
Conclusion
Choosing between imperative and declarative programming is not a simple choice and often involves consideration. Imperative code can give you a lot of control but often at the expense of simplicity, abstracted code that easy to read and maintain. When you need precise control or performance is an primary focus, an imperative approach might make sense. Most other times it probably makes the most sense to use a declarative approach that can lead to cleaner code. With the advent of bundlers, minification, and other optimization tools, small performance improvements become less impactful. As developers, it’s beneficial to be versatile and comfortable with both paradigms, using each where it best fits the problem at hand.
This problem comes from LeetCode. There is no shortage of practice problems out there, but LeetCode is one of the most popular platforms for honing your algorithm design skills. With practice problems, solutions, and a healthy user base to discuss problems with, LeetCode is a great resource.
Problem Solution
The key to this problem is to map the characters to the frequency in which they occur in the string. Whenever you encounter a problem where the word “frequency” is used, there’s a good chance that a map will be the right tool for the job.
Once all of the characters are mapped, we need to extrapolate the individual characters into strings that contain the character repeated the proper number of times. We can then sort those strings and join them into one final string.
Let’s break down the logic into smaller, digestible pieces.
Counting Characters
A flowchart illustrating the logic of counting characters.
Rather than trying to inefficiently group and sort these characters in place, instead, it is much easier to simply count the character frequencies and then create the character groupings we’d like to see later. The map data structure is particularly useful here because it is implemented in a way that allows us to have constant time lookup (i.e. O(1)). So by using a map, when we want to add to a character’s tally, it’s a fast lookup to check if we already have that character in the map.
So, we can iterate through our characters and check if they already exist in our map. If they do, we’ll increment the tally for that character by 1, and if not, we’ll add that character to the map with an initial tally value of 1.
Extrapolating and Sorting
A flowchart illustrating the logic of extrapolating and sorting characters.
Extrapolating the character to a string comprised of the character repeated by its frequency could be its own section in this algorithm, but most mature programming languages have a built-in, declarative way to do this. In JavaScript, we can use String.prototype.repeat to accomplish this.
With the extrapolation logic already taken care of, our logic is as follows: iterate through the map, extrapolate the character, and push that extrapolated string into a sortable data structure, and then sort. The key here is to use an easily-sortable data structure. In JavaScript, arrays have a native Array.prototype.sort method that can be used to declaratively sort items, so we’ll use one to store our extrapolated strings.
Joining
A flowchart illustrating the logic of joining extrapolated characters.
After we’ve sorted our strings, we simply need to join them together into our final result string. Once again, JavaScript has a declarative prototype method called Array.prototype.join that will do this for us. If you’d rather implement the joining logic yourself, you simply need to iterate through the array and concatenate each string to a result string.
JavaScript Implementation
Now that we have our mental model and algorithm in place, translating it to code is fairly trivial. Let’s take a look at a JavaScript implementation.
As you can see, the mapping logic is implemented on lines 2 through 7. We create an empty object to act as our map, use a for loop to iterate through our string, and on each iteration, we use basic object property assignment to update our character frequencies.
The character extrapolation happens on lines 9 through 14. You’ll notice we use a for...in loop to iterate through our object, and on each iteration, we extrapolate our string using the String.prototype.repeat method and we push it to the end of our array. Afterward, we use Array.prototype.sort to sort our strings by length.
Finally, we use Array.prototype.join to combine our array of strings into one final string on line 17.
Efficiency
An algorithm is only as good as its efficiency. An inefficient algorithm is certainly better than nothing during an interview, but typically the “brute force” approach is not going to cut it. So, it’s important to understand how to calculate the efficiencies of your algorithm and how to communicate that information to others.
The efficiency of an algorithm is generally described using Big O Notation and is used to define both time complexity and space complexity.
Time Complexity
For our problem, the mapping is linear (i.e. O(n)) and so is the joining, but the bottleneck here is the sorting. The sorting efficiency depends on the implementation of the JavaScript runtime. Chrome uses the V8 engine, which itself implements Array.prototype.sort using the Timsort algorithm, which on average produces a time complexity of O(n*log(n)). Because these operations are sequential and not nested, the largest complexity dwarfs the others as n (the number of items in the data structure) approaches infinity.
Space Complexity
Inherently, the mapping operation takes up linear space (i.e. O(n)) because, for each character in our string, we are allocating a chunk of memory in our map. On average, the memory used in the mapping will be less n because we will often have repeat characters, but we’re typically only concerned with worst-case scenarios in algorithm problems. The extrapolating portion is also linear because we’re adding an item to our array for each entry in our map. These are the only two parts of the operation that consume additional memory, and since they are both linear, the algorithm as a whole is considered to have linear (i.e. O(n)) space complexity.
Conclusion
Algorithm problems are about recognizing when to use particular logic patterns. To do so, you need to familiarize yourself with the various patterns and combinations of patterns out there.
Mapping characters to the frequency in which they occur is a common pattern that you should become very familiar with. Once you fully understand the strategy and the efficiencies behind it, you’ll start to recognize other areas where it can be properly used.
