<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Jack Chen on Medium]]></title>
        <description><![CDATA[Stories by Jack Chen on Medium]]></description>
        <link>https://medium.com/@passbyvalue?source=rss-9c7de96ecc86------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*ExaxPdWGtAsJE-gUU1Yz2A.png</url>
            <title>Stories by Jack Chen on Medium</title>
            <link>https://medium.com/@passbyvalue?source=rss-9c7de96ecc86------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 00:06:36 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@passbyvalue/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[How to Think Recursively | Solving Recursion Problems in 4 Steps]]></title>
            <link>https://levelup.gitconnected.com/how-to-think-recursively-solving-recursion-problems-in-4-steps-95a6d07aa866?source=rss-9c7de96ecc86------2</link>
            <guid isPermaLink="false">https://medium.com/p/95a6d07aa866</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[recursion]]></category>
            <category><![CDATA[technology]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Jack Chen]]></dc:creator>
            <pubDate>Sun, 12 May 2019 05:48:23 GMT</pubDate>
            <atom:updated>2022-03-04T14:54:45.220Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/680/1*Kmd2j_y80B45B2wv4buzKA.jpeg" /><figcaption>Original comic from Safely Endangered. No idea who created this variant of the meme.</figcaption></figure><h4><strong>Disclaimer</strong></h4><p>This article is not meant to introduce more advanced concepts like dynamic programming. Instead, it will introduce the mentality required to start solving recursive problems.</p><p>The examples are in Javascript, but I’ll write answers in Python and C++ in the bottom of this article.</p><h4><strong>What is recursion</strong></h4><p>Since you are reading this article, I’m assume that you have a vague idea of recursion, so I won’t go deep into the context of it. Personally, I like to think of recursion as the following.</p><blockquote><em>Recursion is a way to solve a problem by solving smaller subproblems.</em></blockquote><h3>Before we start …</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*TjNUK7WL4rJOwH0F" /><figcaption>Photo by <a href="https://unsplash.com/@will0629?utm_source=medium&amp;utm_medium=referral">Will Porada</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p><strong>Stop going through the function calls!</strong></p><p>This is a large hurdle that hampers students when they learn recursion. They try to see what is happening at<strong> every</strong> <strong>single</strong> function call and try to trace each step in their solution.</p><p>You don’t need to know what’s happening in every step. If you want to start solving recursion problems, you must be willing to take a<strong> </strong>leap of a faith. You gotta <strong><em>believeee</em></strong>. Assumptions will need to be made and is necessary for solving these types of problems.</p><h3>How to do it</h3><p>First, let’s do one of the simplest recursion problems you can ever do.</p><h4><strong>Problem: Sum all values from 1 to n</strong></h4><pre>function sumTo(n) {</pre><pre>}</pre><h3><strong>Step 1) Know what your function should do</strong></h3><p>The first step to solve recursion problems, is to know what your function is suppose to do.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*Lck2C_CbnxL4qD5mBmqsgQ.jpeg" /><figcaption>Reader: Do you think I’m an idiot?</figcaption></figure><p>This might seem obvious, but it’s an important step that gets glossed over. You need to think about what your function <strong><em>should do</em>,</strong> not what it<strong> <em>currently does</em>.</strong></p><p>Looking at our sumTo() function, it’s clear that the function <strong><em>should</em></strong> return an integer sum from 1 to n.</p><pre>/*<br>  sumTo() takes an integer n and returns the sum of all integers      from 1 to n<br>*/</pre><pre>function sumTo(n) {</pre><pre>}</pre><h3><strong>Step 2) Pick a subproblem and assume your function already works on it</strong></h3><blockquote><strong>… Subproblems…?</strong></blockquote><p>A <strong><em>sub problem </em></strong>is any problem that is <strong>smaller</strong> than your original problem.</p><p>Our original problem is to sum all values from 1 to n. A subproblem in this case is to sum all numbers up to a value <strong><em>smaller</em></strong> than n.</p><pre>// If sumTo(n) was our original problem, these are all considered subproblems because they are smaller versions of the original problem</pre><pre>sumTo(n-1)<br>sumTo(n-2)<br>sumTo(n-3)<br>...<br>sumTo(1)</pre><p>But to make solving your problem easier, we need to select an <em>appropriate</em> subproblem.</p><p><strong>Picking an appropriate subproblem</strong></p><p>There are many ways to pick a subproblem. A good starting strategy is to choose a subproblem as <strong><em>close</em></strong> to the original as possible. Since we <strong><em>assume</em></strong> that sumTo() function<strong><em> already works</em></strong>, why not pick a value that solves the bulk of the problem for us?</p><p>In this case, since our problem solves for n, then the best subproblem should solve for n-1.</p><p><strong>Using n-1 as our subproblem</strong></p><pre>/*<br>  sumTo() takes an integer and returns an integer n<br>  that is the sum from 1 to n<br>*/<br></pre><pre>// n is our original problem<br>function sumTo (n) {</pre><pre>  // Using n-1 as our subproblem, it returns the sum from 1 to n-1.<br>  const solutionToSubproblem = sumTo(n-1) <br>}</pre><p><strong>But wait! How can we use a function we haven’t defined yet ???</strong></p><p>You are correct, we have not defined anything yet, but that’s what I meant in the beginning of the article. To solve a recursion problem, let’s <strong><em>ASSUME</em></strong> that the function already works for any subproblem we want.</p><p>Because of our subproblem selection, we already have the sum of all values from 1 to n-1. All we need to do now is make that final leap.</p><h3><strong>Step 3) Take the answer to your subproblem, and use it to solve for the original problem.</strong></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GvtZw4QPovl9OhjV0hmabw.jpeg" /></figure><p>We already solved our subproblem. So the next question is …</p><blockquote><strong><em>How do we take the solution to our subproblem, and use it to solve the original problem ?</em></strong></blockquote><p>So far we have solved for 1 to n-1. But how do we use that to solve for n?</p><pre>// n is our original problem<br>function sumTo (n) {</pre><pre>  // Using n-1 as our subproblem, it returns the sum from 1 to n-1.<br>  const solutionToSubproblem = sumTo(n-1) <br>}</pre><p>Let’s think about our original problem again.</p><p>We want to find the sum from 1 to n, and we already have the solution from 1 to n -1.</p><p>How do we get the sum from 1 to n, if we have the solution from 1 to n-1?</p><pre>sumTo(n-1) // 1 + 2  ... n-2 + n-1<br>sumTo(n)   // 1 + 2  ... n-2 + n-1 + n</pre><p>With some basic algebra, all we need to do is add n to the solution of our subproblem, which will solve our original problem.</p><pre>// What we&#39;ve already determined<br>sumTo(n-1) // 1 + 2  ... n-2 + n-1<br>sumTo(n)   // 1 + 2  ... n-2 + n-1 + n</pre><pre>// Using our solution to the subproblem to solve the original<br>sumTo(n-1) + n  // 1 + 2  ... n-2 + n-1 + n<br>sumTo(n)        // 1 + 2  ... n-2 + n-1 + n</pre><p>Or in code …</p><pre>function sumTo (n) { // n is our original problem<br>  const solutionToSubproblem = sumTo(n-1) // n-1 is our subproblem<br> <br>  return solutionToSubproblem + n<br>}</pre><p>As you saw, we took the solution to our subproblem and found how it’s used to solve the original problem. This is known as finding the<strong> </strong><em>recurrence relation.</em></p><h3><strong>Step 4) You have already solved 99% of the problem. The remaining 1%? Base case.</strong></h3><p>Your function is calling itself, so it will probably run forever. That is why we need to add a base case to stop it.</p><p><strong>What is a base case and how do we determine a base case?</strong></p><p>A base case is a way for us to stop the recursion. Usually, it can be a simple if-else statement in the beginning of the function.</p><p>The condition prevents more function calls if it has reached its base case. To pick a base case, think of the following.</p><blockquote><em>“What is the </em><strong>EASIEST POSSIBLE PROBLEM</strong><em> that requires no extra calculation?”</em></blockquote><p>In our case, that would be n = 0.</p><p>It’s obvious that the sum of all values from 0 to 0, is 0, so why bother doing more recursion? That’s where we define our base case.</p><pre>function sumTo (n) {<br>  if (n === 0) { return 0 }<br>  const solutionToSubproblem = sumTo(n-1)<br> <br>  return solutionToSubproblem + n<br>}</pre><p>Now that we have a base case. There is now a point where the recursion stops.</p><p><strong>THAT’S IT</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/658/1*LBWMmAYiohGyvPRgnteOEw.png" /><figcaption>VICTORY SCREECH !!! — SpongeBob SquarePants S3E1</figcaption></figure><p>That’s all there is to our answer. In summary, solving the recursion problems involves the following</p><ul><li>Keeping in mind what the function <strong><em>should</em></strong> do, not what it currently does</li><li>Identifying the proper subproblems</li><li>Use the solution to your subproblems to solve the original problem</li><li>Writing a base case</li></ul><h3>More examples</h3><h4><strong>Problem: Reverse a string</strong></h4><pre>function reverse(s) {</pre><pre>}</pre><p>What <strong><em>should</em></strong> the function do? The function <strong><em>should</em></strong> return a reversed copy of a string.</p><pre>// Reverses a string s<br>function reverse(s) {</pre><pre>}</pre><p>Our problem is to reverse a string s. Let’s think of a subproblem that would make solving this problem easy. Let’s use “<em>Hello</em>” as our main problem.</p><p>Again, let’s <strong><em>assume</em></strong> reverse() already works. To make our lives easier, we pick a subproblem that solves the bulk of the problem for us. In this case, let’s just call reverse() on everything but the first letter.</p><pre>reverse(&quot;Hello&quot;) // &quot;Hello&quot; is our original problem&quot;<br>reverse(&quot;ello&quot;)  // &quot;ello&quot; can be used as our subproblem</pre><blockquote>Incase you were wondering why I picked “ello” as the subproblem, just note that you could also choose “Hell” as the subproblem too. I choose this “ello” as the subproblem since it’s going to lead to <em>slightly</em> easier to grasp code. (Feel free to try alternative subproblem selections)</blockquote><p>How do we use our subproblem to solve our original? In this case, we can append the first letter of our original problem to the end of the subproblem solution.</p><pre>// What we determined so far<br>reverse(&quot;Hello&quot;) // &quot;olleH&quot;<br>reverse(&quot;ello&quot;)  // &quot;olle&quot;</pre><pre>// Using our subproblem to solve the original<br>reverse(&quot;Hello&quot;)      // &quot;olleH&quot;<br>reverse(&quot;ello&quot;) + &quot;H&quot; // &quot;olleH&quot;</pre><p>Using our example, let’s abstract this answer to work for any string s.</p><pre>function reverse (s) {<br>  const subproblem = s.slice(1, s.length) // exclude first letter<br>  const reversedSubproblem = reverse(subproblem)</pre><pre>  return reversedSubproblem + s[0]<br>}</pre><p>Lastly, let’s determine our base case. For our problem, what is the <strong><em>simplest</em></strong> value that we can pass in that <strong><em>doesn’t need</em></strong> extra computation? The answer is the empty string. What is the reverse of an empty string? Well, the empty string of course.</p><pre>function reverse (s) {<br>  if (s === &#39;&#39;) { return &#39;&#39; } // Base case</pre><pre>  const subproblem = s.slice(1, s.length)<br>  const reversedSubproblem = reverse(subproblem)</pre><pre>  return reversedSubproblem + s[0]<br>}</pre><h4>Problem: Return the nth term in the Fibonacci Sequence</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*2v-qYJX-a1NITv9C" /><figcaption>Photo by <a href="https://unsplash.com/@junglerolf?utm_source=medium&amp;utm_medium=referral">rolf neumann</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Ah yes, the infamous Fibonacci Problem …</p><pre>// Fibonacci Sequence<br>0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...</pre><pre>function fibTerm(n) {</pre><pre>}</pre><p>Once you familiarize how the fibonacci sequence works, you will notice that the nth term is the sum of its two <strong><em>previous</em></strong> terms.</p><p>For example …</p><pre>5 is the sum of the two previous values 3 and 2.<br>34 is the sum of the two previous values 21 and 13.<br>233 is the sum of the two previous values 144 and 89.</pre><p>Unlike our other problems, our original problem requires us to solve <strong>two subproblems</strong>.</p><pre>// Fibonacci Sequence (using n = 7 as an example)<br>0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...<br>               ^  ^   ^<br>              n-2 n-1 n</pre><pre>The nth term, is the sum of the n-1 and n-2 term.</pre><p><strong><em>Assuming</em></strong> that our function already works, we use it to calculate the two previous terms.</p><pre>// Fibonacci Sequence<br>0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...</pre><pre>function fibTerm(n) {<br>  const term1 = fibTerm(n-1)  // Our two sub problems<br>  const term2 = fibTerm(n-2)<br>}</pre><p>To solve our original problem, let’s return the sum of our two subproblems.</p><pre>// Fibonacci Sequence<br>0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...</pre><pre>function fibTerm(n) {<br>  const term1 = fibTerm(n-1)<br>  const term2 = fibTerm(n-2)<br>  <br>  // Solving the original problem using our subproblem solutions<br>  return term1 + term2 <br>}</pre><p>Finding the base case might be a bit tricky. In our case, we have two base cases, n = 0 and n = 1. The reason is that those values don’t have two previous terms to calculate from.</p><p>Using n = 0 and n = 1 as our base case, we complete our function.</p><pre>// Fibonacci Sequence<br>0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...</pre><pre>function fibTerm(n) {<br>  if (n === 0) { return 0 }<br>  if (n === 1) { return 1 }</pre><pre>  const term1 = fibTerm(n-1)<br>  const term2 = fibTerm(n-2)</pre><pre>  return term1 + term2 // Solving the original problem<br>}</pre><h3>C++ / Python Solutions</h3><p><strong>Problem: Sum from 1 to n</strong></p><pre>// C++<br>int sumTo(int n) {<br>  if (n == 1) { return 1 }<br>  return n + sumTo(n)<br>}</pre><pre>// Python<br>def sumTo(n) {<br>  if (n == 1 ) { return 1 }<br>  return n + sumTo(n)<br>}</pre><p><strong>Problem: Reverse a string from 1 to n</strong></p><pre>// C++<br>string reverse(string n) {<br>  if (n == &#39;&#39;) { return &#39;&#39;}<br>  return reverse(n.substr(1, n.length()-1 ) + n[0]<br>}</pre><pre>// Python<br>def reverse(n) {<br>  if (n == &#39;&#39;) { return &#39;&#39;}<br>  return reverse(n[1:]) + n[0]<br>}</pre><p><strong>Problem: Find the nth term of the Fibonacci Sequence</strong></p><pre>// C++<br>int fibTerm(int n) {<br>  if (n == 0) { return 0 }<br>  if (n == 1) { return 1 }<br>  return fibTerm(n-1) + fibTerm(n-2)<br>}</pre><pre>// Python<br>def fibTerm(n) {<br>  if (n == 0) { return 0 }<br>  if (n == 1) { return 1 }<br>  return fibTerm(n-1) + fibTerm(n-2)<br>}</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=95a6d07aa866" width="1" height="1" alt=""><hr><p><a href="https://levelup.gitconnected.com/how-to-think-recursively-solving-recursion-problems-in-4-steps-95a6d07aa866">How to Think Recursively | Solving Recursion Problems in 4 Steps</a> was originally published in <a href="https://levelup.gitconnected.com/">Level Up Coding</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>