开源日报 每天推荐一个 GitHub 优质开源项目和一篇精选英文科技或编程文章原文,坚持阅读《开源日报》,保持每日学习的好习惯。
今日推荐开源项目:《幻灯片 fusuma》
今日推荐英文原文:《When to loop? When to recurse?》
开源日报第428期:《幻灯片 fusuma》
今日推荐开源项目:《幻灯片 fusuma》传送门:GitHub链接
推荐理由:简单方便的使用 Markdown 创造幻灯片。你只需要写好想要作为幻灯片展示的 Markdown 并按照顺序整理好目录结构,再写好需要的 CSS 文件之后,这个项目就能够让你简单的使用浏览器展示它们,或者是把它整体导出为一个 pdf 文件。不管怎么说,它都能让你在需要把 Markdown 作为幻灯片展示的时候省下不少功夫。
今日推荐英文原文:《When to loop? When to recurse?》作者:Faith Chikwekwe
原文链接:https://medium.com/@faith.chikwekwe/when-to-loop-when-to-recurse-b786ad8977de
推荐理由:递归可以做循环能做的工作,也能做循环不能做的工作,只有在需要的时候,才应该使用递归——最起码给别人看代码的时候,循环看起来比较好懂。

When to loop? When to recurse?

开源日报第428期:《幻灯片 fusuma》
Well known Google joke featuring recursion

Cracking the Coding Interview states that “All recursive algorithms can [also] be implemented iteratively…” in its section on approaching technical interview problems using recursion.

Solving a Python problem iteratively might include using a for or while loop. These are some of the most common tools used for incremental problem solving in any coding language. Loops are great because a lot of the time, their implementation is intuitive and straightforward.

However, there are times when iterative solutions can turn into barely readable nightmares.
开源日报第428期:《幻灯片 fusuma》
Trying to write highly nested and complicated code on a whiteboard with an interviewer’s inquisitive gaze inspecting your work can be a surefire way to trip yourself up in a technical interview.

While switching from looping to recursion will not always make your code better, it is a great tool to have in your toolbox.

For a while, I was afraid of learning recursion. Upon learning that problems with a recursive solution inevitably have an iterative one as well, I was fixated on trying to solve every technical problem with loops.

However, as my technical interview skills grew, I encountered many LeetCode and HackerRank problems that cried out for recursion with their complexity. It was time to broaden the tools at my disposal.

What are Loops?

开源日报第428期:《幻灯片 fusuma》
Diagram of a for loop and a while loop.

A loop is used to perform a repetitive block of code as many times as necessary for the program. For loops, like the one in the example above iterate over a sequence. We generally use for loops when we know how many times we need to execute a block of code. In the above example, we only need to do lines 2 and 3 for the number of names in name_list.

We might also need to loop for an undetermined number of times or until a certain condition is met. This might be a good time to use a while loop. One way to return the length of a non-iterable Linked List might involve using a while loop to traverse all nodes like in the example above.

Okay, so what is Recursion?

开源日报第428期:《幻灯片 fusuma》
Image from https://medium.com/@williambdale/recursion-the-pros-and-cons-76d32d75973a

A big difference between recursion and iteration is the way that they end. While a loop executes the block of code, checking each time to see if it is at the end of the sequence, there is no such sequential end for recursive code.

Like the horrifying Winnie the Pooh comic above, a recursive function could go on forever without a condition to put it out of its misery.
开源日报第428期:《幻灯片 fusuma》
Showing the base case and the recursive call in a recursive function on the factorial example. Image from https://www.slideshare.net/alhazmy13/data-structures-part5-recursion

A recursive function like the one above consists of two parts: the recursive call and the base case.

The base case (or bases cases sometimes) is the condition that checks to see if we have gotten the information that we need out of our function. Every recursive function should have at least one base case, though there may be multiple.

In the factorial example above, we have reached the end of our necessary recursive calls when we get to the number 0.

The recursive call as you may have suspected is when the function calls itself adding to the recursive call stack.

Stacks are LIFO (Last In First Out) objects meaning that the last item that was added to the top of the stack is the first one to be removed from the stack later on.

开源日报第428期:《幻灯片 fusuma》
Diagram from https://medium.com/@charlie.b.ohara/recursion-revealed-f8543e4dad1c

When Should I Use Recursion?

Recursion is made for solving problems that can be broken down into smaller, repetitive problems. It is especially good for working on things that have many possible branches, and are too complex for an iterative approach.

One good example of this would be searching through a file system. When you start at the root folder, and then you could search through all the files and folders within that one. After that you would enter each folder and search through each folder inside of that.
开源日报第428期:《幻灯片 fusuma》

Recursion works well for this type of structure, because you can search multiple branching paths without having to include many different checks and conditions for every possibility.

For those of your who are familiar with data structures, you might notice that the image above of the file system looks a lot like a tree structure.

Trees and graphs are another time when recursion is the best and easiest way to do traversal.

Should I Always Use Recursion?

Recursion seems really useful! Maybe I should use it all the time?

Well, like anything recursion is best in doses. Recursion is a useful tool, but it can increase memory usage.

So let’s go back to the factorial call stack image from above. Every time we add a new call to the stack, we are increasing the amount of memory that we are using. If we are analyzing the algorithm using Big O notation, then we might note that this increases our space complexity.

There are times when we might want to pay this cost in order to get a short, useful algorithm, like when we are traversing a tree. But there are other times, when there may be better, more efficient ways of solving this problem.

For many small projects, the call stack won’t hamper you program very much. However, once your program starts making many recursive calls, then you might want to consider the potential impact of your large call stack.
开源日报第428期:《幻灯片 fusuma》
Stack of Books. Photo by John-Mark Smith on Unsplash

Another thing to consider is that understanding and reading your code might sometimes be easier to do in an iterative solution.

Using recursion is great because it takes many of the incremental sub problems out of your hands.

But when you are try to fully understand the sub problems that you are solving and how they are being solved, it might be worth implementing an iterative solution. If this is not a feasible route, then at the very least diagram the recursive process undertaken by your code to deepen your knowledge.
下载开源日报APP:https://openingsource.org/2579/
加入我们:https://openingsource.org/about/join/
关注我们:https://openingsource.org/about/love/