kgashok/recursive.html

## recursive.html
<h2 id="table-of-contents">Table of Contents</h2>

<p><div class="toc">
<ul>
<li><ul>
<li><a href="#table-of-contents">Table of Contents</a><ul>
<li><a href="#why-recursion-pros-and-cons">Why Recursion? - Pros and Cons</a><ul>
<li><a href="#quiz-1">Quiz 1</a><ul>
<li><a href="#httpjmphalfofreckg">http://j.mp/halfOfRecKG</a></li>
</ul>
</li>
<li><a href="#quiz-2">Quiz 2</a></li>
</ul>
</li>
<li><a href="#recursive-natural-number-summation">Recursive Natural Number Summation</a><ul>
<li><a href="#httpjmpnaturalreckg">http://j.mp/naturalRecKG</a></li>
<li><a href="#output">Output</a></li>
</ul>
</li>
<li><a href="#recursive-power-calculation">Recursive Power Calculation</a><ul>
<li><a href="#httpjmppowerreckg">http://j.mp/powerRecKG</a></li>
</ul>
</li>
<li><a href="#recursive-factorial">Recursive Factorial</a><ul>
<li><a href="#httpjmpfactorialreckg">http://j.mp/factorialRecKG</a></li>
</ul>
</li>
<li><a href="#recursive-gcd-of-two-numbers">Recursive GCD of Two Numbers</a><ul>
<li><a href="#httpjmpgcdreckg">http://j.mp/gcdRecKG</a></li>
</ul>
</li>
<li><a href="#recursive-fibonacci-series">Recursive Fibonacci Series</a><ul>
<li><a href="#httpjmpfiboreckg">http://j.mp/fiboRecKG</a></li>
<li><a href="#output-1">Output</a></li>
</ul>
</li>
<li><a href="#recursive-sum-of-integer-array">Recursive Sum of Integer Array</a><ul>
<li><a href="#httpjmparraysumreckg">http://j.mp/arraysumRecKG</a></li>
</ul>
</li>
<li><a href="#recursive-palindrome">Recursive Palindrome</a><ul>
<li><a href="#httpjmppalindromereckg">http://j.mp/palindromeRecKG</a></li>
<li><a href="#output-2">Output</a></li>
</ul>
</li>
<li><a href="#recursive-palindrome-number">Recursive Palindrome Number</a></li>
<li><a href="#recursive-linked-list">Recursive Linked List</a><ul>
<li><a href="#httpjmplinkedreckg">http://j.mp/linkedRecKG</a></li>
<li><a href="#output-3">Output</a></li>
</ul>
</li>
<li><a href="#alternative-fibonacci">Alternative Fibonacci</a><ul>
<li><a href="#output-4">Output</a></li>
</ul>
</li>
<li><a href="#recursive-halfof">Recursive HalfOf</a><ul>
<li><a href="#httpjmphalfofreckg-1">http://j.mp/halfOfRecKG</a></li>
</ul>
</li>
<li><a href="#tower-of-hanoi">Tower of Hanoi</a><ul>
<li><a href="#httpjmptowerofhanoicc">http://j.mp/towerOfHanoiCC</a></li>
</ul>
</li>
<li><a href="#right-numeric-triangle">Right Numeric Triangle</a><ul>
<li><a href="#httpjmprecrighttriangle">http://j.mp/recRightTriangle</a></li>
</ul>
</li>
<li><a href="#recursive-sorts">Recursive Sorts</a><ul>
<li><a href="#selection-sort">Selection Sort</a><ul>
<li><a href="#httpjmpselectionsortcc">http://j.mp/selectionSortCC</a></li>
</ul>
</li>
<li><a href="#insertion-sort">Insertion Sort</a><ul>
<li><a href="#httpjmpinsertionsortcc">http://j.mp/insertionSortCC</a></li>
</ul>
</li>
<li><a href="#merge-sort">Merge Sort</a></li>
<li><a href="#quick-sort">Quick Sort</a></li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
</p>

<ul>
<li><a href="#table-of-contents">Table of Contents</a> <br>
<ul><li><a href="#why-recursion---pros-and-cons">Why Recursion? - Pros and Cons</a> <br>
<ul><li><a href="#quiz-1">Quiz 1</a>  </li>
<li><a href="#quiz-2">Quiz 2</a>  </li></ul></li>
<li><a href="#recursive-natural-number-summation">Recursive Natural Number Summation</a> <br>
<ul><li><a href="#httpjmpnaturalreckg">http://j.mp/naturalRecKG</a>  </li>
<li><a href="#output">Output</a>  </li></ul></li>
<li><a href="#recursive-power-calculation">Recursive Power Calculation</a> <br>
<ul><li><a href="#httpjmppowerreckg">http://j.mp/powerRecKG</a>  </li></ul></li>
<li><a href="#recursive-factorial">Recursive Factorial</a> <br>
<ul><li><a href="#httpjmpfactorialreckg">http://j.mp/factorialRecKG</a>  </li></ul></li>
<li><a href="#recursive-gcd-of-two-numbers">Recursive GCD of Two Numbers</a> <br>
<ul><li><a href="#httpjmpgcdreckg">http://j.mp/gcdRecKG</a>  </li></ul></li>
<li><a href="#recursive-fibonacci-series">Recursive Fibonacci Series</a> <br>
<ul><li><a href="#httpjmpfiboreckg">http://j.mp/fiboRecKG</a>  </li>
<li><a href="#output">Output</a>  </li></ul></li>
<li><a href="#recursive-sum-of-integer-array">Recursive Sum of Integer Array</a> <br>
<ul><li><a href="#httpjmparraysumreckg">http://j.mp/arraysumRecKG</a>  </li></ul></li>
<li><a href="#recursive-palindrome">Recursive Palindrome</a> <br>
<ul><li><a href="#httpjmppalindromereckg">http://j.mp/palindromeRecKG</a>  </li>
<li><a href="#output">Output</a>  </li></ul></li>
<li><a href="#recursive-palindrome-number">Recursive Palindrome Number</a>  </li>
<li><a href="#recursive-linked-list">Recursive Linked List</a> <br>
<ul><li><a href="#httpjmplinkedreckg">http://j.mp/linkedRecKG</a>  </li>
<li><a href="#output">Output</a>  </li></ul></li>
<li><a href="#alternative-fibonacci">Alternative Fibonacci</a> <br>
<ul><li><a href="#output">Output</a>  </li></ul></li>
<li><a href="#recursive-halfof">Recursive HalfOf</a> <br>
<ul><li><a href="#httpjmphalfofreckg">http://j.mp/halfOfRecKG</a>  </li></ul></li>
<li><a href="#tower-of-hanoi">Tower of Hanoi</a> <br>
<ul><li><a href="#httpjmptowerofhanoicc">http://j.mp/towerOfHanoiCC</a>  </li></ul></li>
<li><a href="#right-numeric-triangle">Right Numeric Triangle</a> <br>
<ul><li><a href="#httpjmprecrighttriangle">http://j.mp/recRightTriangle</a>  </li></ul></li>
<li><a href="#recursive-sorts">Recursive Sorts</a> <br>
<ul><li><a href="#selection-sort">Selection Sort</a> <br>
<ul><li><a href="#httpjmpselectionsortcc">http://j.mp/selectionSortCC</a>  </li></ul></li>
<li><a href="#insertion-sort">Insertion Sort</a> <br>
<ul><li><a href="#httpjmpinsertionsortcc">http://j.mp/insertionSortCC</a>  </li></ul></li>
<li><a href="#merge-sort">Merge Sort</a>  </li>
<li><a href="#quick-sort">Quick Sort</a>  </li></ul></li></ul></li>
</ul>

<h3 id="why-recursion-pros-and-cons">Why Recursion? - Pros and Cons</h3>

<p><em>“Recursive functions are confusing, elegant and fascinating, all the same time!”</em></p>

<p>Some programs and/or computer algorithms are more readable, concise and less error prone when implemented as recursive calls. The <strong>downside:</strong> low performance and high memory usage, especially when there are innumerable recursive calls, sometimes resulting in memory overflow conditions on the stack.</p>

<p>Almost any iterative code (containing loops) can be re-written as a smaller, simpler (<em>but not always intuitive</em>) recursive program. The general recipe for writing a recursive calls can be broadly categorized as three steps:</p>

<ol>
<li>Determine the <strong>TERMINAL CONDITIONS</strong> under which the recursive calls will terminate and return. This is usually a combination of <code>if</code> statement and a<code>return</code> statement </li>
<li>Do some computation as required by the problem (e.g. add, multiply or printing) including determining parameter(s) for the next recursive call</li>
<li>A <code>return</code> statement containing a recursive function call with new parameters</li>
</ol>

<p>Also review - <a href="https://goo.gl/photos/z6LBsEh6NcZJ3AvN7">https://goo.gl/photos/z6LBsEh6NcZJ3AvN7</a></p>


<h4 id="quiz-1">Quiz 1</h4>

<blockquote>
  <h5 id="httpjmphalfofreckg"><a href="http://j.mp/halfOfRecKG">http://j.mp/halfOfRecKG</a></h5>

  <p>Given an integer number, write a recursive function <code>halfOf</code> which will generate a sequence of numbers that will be progressively <em>half of</em> what the previous number was. The program must terminate when the value of the number in the sequence is zero. For e.g. <code>halfOf (21) = 21 10 5 2 1</code>. <br>
  To visualize the solution for this exercise, click <a href="http://j.mp/halfOfV">http://j.mp/halfOfV</a></p>
</blockquote>


<h4 id="quiz-2">Quiz 2</h4>


<pre class="prettyprint"><code class="language-c hljs "><span class="hljs-preprocessor">#include &lt;stdio.h&gt; </span>
<span class="hljs-keyword">int</span> main () {
    <span class="hljs-keyword">int</span> x, num = <span class="hljs-number">5</span>;
    x = call(num);
    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"%d\n"</span>, x);
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}

<span class="hljs-keyword">int</span> call(<span class="hljs-keyword">int</span> num) {
    <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> x = <span class="hljs-number">1</span>, y;
    <span class="hljs-keyword">if</span> (num &gt;<span class="hljs-number">0</span>) {
        x = x+num-<span class="hljs-number">1</span>;
        y = call(num-<span class="hljs-number">1</span>)+<span class="hljs-number">2</span>;
    }
    <span class="hljs-keyword">return</span> x;
}</code></pre>

<p>The output is  <br>
<code>A) 10  B) 8 C) 12 D) 11</code></p>


<h3 id="recursive-natural-number-summation">Recursive Natural Number Summation</h3>


<h4 id="httpjmpnaturalreckg"><a href="http://j.mp/naturalRecKG">http://j.mp/naturalRecKG</a></h4>


<pre class="prettyprint"><code class="language-c hljs ">
<span class="hljs-preprocessor">#include &lt;stdio.h&gt; </span>

<span class="hljs-keyword">int</span> naturalSum (<span class="hljs-keyword">int</span> n) {
    <span class="hljs-keyword">if</span> (n == <span class="hljs-number">1</span>)  <span class="hljs-comment">// TERMINAL CONDITION </span>
        <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;
    <span class="hljs-keyword">return</span> n + naturalSum(n-<span class="hljs-number">1</span>);
}

<span class="hljs-keyword">int</span> main () {
    <span class="hljs-keyword">int</span> n = <span class="hljs-number">10</span>;
    <span class="hljs-keyword">int</span> sum = naturalSum (n);
    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"sum of %d natural numbers is %d\n"</span>, n, sum);
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}
</code></pre>


<h4 id="output">Output</h4>


<pre class="prettyprint"><code class=" hljs vhdl">sum <span class="hljs-keyword">of</span> <span class="hljs-number">10</span> <span class="hljs-typename">natural</span> numbers <span class="hljs-keyword">is</span> <span class="hljs-number">55</span></code></pre>


<h3 id="recursive-power-calculation">Recursive Power Calculation</h3>


<h4 id="httpjmppowerreckg"><a href="http://j.mp/powerRecKG">http://j.mp/powerRecKG</a></h4>


<pre class="prettyprint"><code class="language-c hljs "><span class="hljs-preprocessor">#include &lt;stdio.h&gt; </span>

<span class="hljs-keyword">int</span> power (<span class="hljs-keyword">int</span> x, <span class="hljs-keyword">int</span> y) {
    <span class="hljs-keyword">if</span> (y == <span class="hljs-number">0</span>)     <span class="hljs-comment">// TERMINAL CONDITION</span>
        <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;

    <span class="hljs-keyword">return</span> x * power (x, y-<span class="hljs-number">1</span>);
}

<span class="hljs-keyword">int</span> main () {

    <span class="hljs-keyword">int</span> x = <span class="hljs-number">5</span>;
    <span class="hljs-keyword">int</span> y = <span class="hljs-number">3</span>;
    <span class="hljs-keyword">int</span> result = power (x, y);
    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"%d to the power of %d is = %d\n"</span>, x, y, result);
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;

}</code></pre>


<h3 id="recursive-factorial">Recursive Factorial</h3>


<h4 id="httpjmpfactorialreckg"><a href="http://j.mp/factorialRecKG">http://j.mp/factorialRecKG</a></h4>


<pre class="prettyprint"><code class="language-c hljs "><span class="hljs-preprocessor">#include &lt;stdio.h&gt; </span>

<span class="hljs-keyword">int</span> factorial (<span class="hljs-keyword">int</span> n) {
    <span class="hljs-keyword">if</span> ( n == <span class="hljs-number">0</span> || n == <span class="hljs-number">1</span>)  <span class="hljs-comment">// TERMINAL CONDITION</span>
        <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;
    <span class="hljs-keyword">return</span> n * factorial (n-<span class="hljs-number">1</span>);
}

<span class="hljs-keyword">int</span> main (<span class="hljs-keyword">int</span> argc, <span class="hljs-keyword">char</span>** argv) {

    <span class="hljs-keyword">int</span> number = atoi (argv[<span class="hljs-number">1</span>]); <span class="hljs-comment">// or do scanf()</span>
    <span class="hljs-keyword">int</span> fval   = factorial(number);
    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"The factorial of %d is %d\n"</span>, number, fval);

    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}</code></pre>


<h3 id="recursive-gcd-of-two-numbers">Recursive GCD of Two Numbers</h3>


<h4 id="httpjmpgcdreckg"><a href="http://j.mp/gcdRecKG">http://j.mp/gcdRecKG</a></h4>


<pre class="prettyprint"><code class="language-c hljs ">
<span class="hljs-preprocessor">#include &lt;stdio.h&gt; </span>

<span class="hljs-keyword">int</span> gcd (<span class="hljs-keyword">int</span> a, <span class="hljs-keyword">int</span> b) {
    <span class="hljs-keyword">if</span> (b==<span class="hljs-number">0</span>)     <span class="hljs-comment">// TERMINAL CONDITION</span>
        <span class="hljs-keyword">return</span> a;

    <span class="hljs-keyword">return</span> gcd(b, a%b);
}

<span class="hljs-keyword">int</span> main () {

    <span class="hljs-keyword">int</span> x = <span class="hljs-number">366</span>;
    <span class="hljs-keyword">int</span> y = <span class="hljs-number">60</span>;

    <span class="hljs-keyword">int</span> result = gcd (x, y);
    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"GCD of %d and %d is %d\n"</span>, x, y, result);
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}
</code></pre>


<h3 id="recursive-fibonacci-series">Recursive Fibonacci Series</h3>


<h4 id="httpjmpfiboreckg"><a href="http://j.mp/fiboRecKG">http://j.mp/fiboRecKG</a></h4>

<p>Here’s a video recording from Khan Academy - worth understanding how it unfolds - <a href="http://j.mp/fiboKG">http://j.mp/fiboKG</a></p>


<pre class="prettyprint"><code class="language-c hljs "><span class="hljs-preprocessor">#include&lt;stdio.h&gt;</span>

<span class="hljs-keyword">int</span> fibonacci_rec(<span class="hljs-keyword">int</span> n) {
   <span class="hljs-keyword">if</span> ( n == <span class="hljs-number">0</span> )    <span class="hljs-comment">// TERMINAL CONDITION_1</span>
      <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
   <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ( n == <span class="hljs-number">1</span> ) <span class="hljs-comment">// TERMINAL CONDITION_2</span>
      <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;
   <span class="hljs-keyword">else</span>
      <span class="hljs-keyword">return</span> fibonacci_rec(n-<span class="hljs-number">1</span>) + fibonacci_rec(n-<span class="hljs-number">2</span>);
}

<span class="hljs-keyword">int</span> main() {
   <span class="hljs-keyword">int</span> n, i = <span class="hljs-number">0</span>, c;
   <span class="hljs-built_in">scanf</span>(<span class="hljs-string">"%d"</span>,&amp;n);
   <span class="hljs-built_in">printf</span>(<span class="hljs-string">"Fibonacci series\n"</span>);
   <span class="hljs-keyword">for</span> ( c = <span class="hljs-number">1</span> ; c &lt;= n ; c++ ) {
      <span class="hljs-built_in">printf</span>(<span class="hljs-string">"%d "</span>, fibonacci_rec(i));
      i++;
   }
   <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}</code></pre>


<h4 id="output-1">Output</h4>


<pre class="prettyprint"><code class=" hljs mathematica"><span class="hljs-number">13</span>
<span class="hljs-keyword">Fibonacci</span> series
<span class="hljs-number">0</span> <span class="hljs-number">1</span> <span class="hljs-number">1</span> <span class="hljs-number">2</span> <span class="hljs-number">3</span> <span class="hljs-number">5</span> <span class="hljs-number">8</span> <span class="hljs-number">13</span> <span class="hljs-number">21</span> <span class="hljs-number">34</span> <span class="hljs-number">55</span> <span class="hljs-number">89</span> <span class="hljs-number">144</span></code></pre>


<h3 id="recursive-sum-of-integer-array">Recursive Sum of Integer Array</h3>


<h4 id="httpjmparraysumreckg"><a href="http://j.mp/arraysumRecKG">http://j.mp/arraysumRecKG</a></h4>


<pre class="prettyprint"><code class=" hljs axapta"><span class="hljs-preprocessor">#include &lt;stdio.h&gt; </span>

<span class="hljs-keyword">int</span> rec_sum (<span class="hljs-keyword">int</span>* s, <span class="hljs-keyword">int</span> size) {
    <span class="hljs-keyword">if</span> (size == <span class="hljs-number">0</span>)  <span class="hljs-comment">// TERMINAL CONDITION</span>
        <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;

    <span class="hljs-keyword">int</span> sumval = *s; <span class="hljs-comment">// get element</span>
    <span class="hljs-keyword">return</span> sumval + rec_sum(++s, size-<span class="hljs-number">1</span>);
}

<span class="hljs-keyword">int</span> main () {
    <span class="hljs-keyword">int</span> s[<span class="hljs-number">7</span>] = {<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">4</span>, <span class="hljs-number">5</span>, <span class="hljs-number">6</span>, <span class="hljs-number">7</span>};
    <span class="hljs-keyword">int</span> <span class="hljs-keyword">sum</span>  = rec_sum (s, <span class="hljs-number">7</span>);

    printf (<span class="hljs-string">"The sum is %d\n"</span>, <span class="hljs-keyword">sum</span>);
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}</code></pre>


<h3 id="recursive-palindrome">Recursive Palindrome</h3>


<h4 id="httpjmppalindromereckg"><a href="http://j.mp/palindromeRecKG">http://j.mp/palindromeRecKG</a></h4>


<pre class="prettyprint"><code class="language-c hljs "><span class="hljs-preprocessor">#include &lt;stdio.h&gt; </span>
<span class="hljs-preprocessor">#include &lt;string.h&gt; </span>

<span class="hljs-keyword">int</span> palin_rec (<span class="hljs-keyword">char</span> *s) {
    <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> i   = <span class="hljs-number">0</span>;

    <span class="hljs-keyword">int</span> front      = i;
    <span class="hljs-keyword">int</span> back       = <span class="hljs-built_in">strlen</span>(s)-i-<span class="hljs-number">1</span>;

    <span class="hljs-keyword">if</span> (front &gt;= back)   <span class="hljs-comment">// TERMINAL CONDITION_1</span>
        <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;

    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"%c == %c? // "</span>, s[front], s[back]);

    <span class="hljs-keyword">if</span> (s[front] != s[back]) {  <span class="hljs-comment">// TERMINAL CONDITION_2</span>
        <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    }

    i++;
    <span class="hljs-keyword">return</span> palin_rec (s);

}

<span class="hljs-keyword">int</span> main () {

    <span class="hljs-keyword">char</span> input[<span class="hljs-number">30</span>];
    <span class="hljs-built_in">scanf</span> (<span class="hljs-string">"%s"</span>, input);

    <span class="hljs-keyword">char</span>* front = input;
    <span class="hljs-keyword">char</span>* back  = input + <span class="hljs-built_in">strlen</span>(input)-<span class="hljs-number">1</span>;

    <span class="hljs-keyword">int</span> res = palin_rec (input);

    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"%s is a palindrome: %s\n "</span>, input,
        (res==<span class="hljs-number">1</span>? <span class="hljs-string">"True"</span> : <span class="hljs-string">"False"</span>));

    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}</code></pre>


<h4 id="output-2">Output</h4>


<pre class="prettyprint"><code class=" hljs ruby">m == m? <span class="hljs-regexp">//</span> a == a? <span class="hljs-regexp">//</span> l == l? <span class="hljs-regexp">//</span> a == a? <span class="hljs-regexp">//</span>
malayalam is a <span class="hljs-symbol">palindrome:</span> <span class="hljs-constant">True</span>

a == a? <span class="hljs-regexp">//</span> b == b? <span class="hljs-regexp">//</span> c == c? <span class="hljs-regexp">//</span> d == f? <span class="hljs-regexp">//</span>
abcdefcba is a <span class="hljs-symbol">palindrome:</span> <span class="hljs-constant">False</span></code></pre>


<h3 id="recursive-palindrome-number">Recursive Palindrome Number</h3>

<p>For checking whether a number is a <strong>palindrome number</strong>, along with the same recursive function above, use the following main() function: </p>


<pre class="prettyprint"><code class="language-c hljs "><span class="hljs-preprocessor">#include &lt;string.h&gt;  <span class="hljs-comment">// for sprintf () function call</span></span>
<span class="hljs-keyword">int</span> main () {

    <span class="hljs-keyword">int</span> i = <span class="hljs-number">23044032</span>;
    <span class="hljs-keyword">char</span> input[<span class="hljs-number">30</span>];
    <span class="hljs-built_in">sprintf</span> (input, <span class="hljs-string">"%d"</span>, i); <span class="hljs-comment">// buf ==  "23044032"; </span>

    <span class="hljs-keyword">int</span> res = palin_rec (input);
    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"%s is a palindrome: %s\n "</span>, input,
        (res==<span class="hljs-number">1</span>? <span class="hljs-string">"True"</span> : <span class="hljs-string">"False"</span>));

    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}</code></pre>


<h3 id="recursive-linked-list">Recursive Linked List</h3>


<h4 id="httpjmplinkedreckg"><a href="http://j.mp/linkedRecKG">http://j.mp/linkedRecKG</a></h4>


<pre class="prettyprint"><code class="language-c hljs "><span class="hljs-preprocessor">#include &lt;stdio.h&gt; </span>
<span class="hljs-preprocessor">#include &lt;stdlib.h&gt; </span>

<span class="hljs-keyword">struct</span> node {
    <span class="hljs-keyword">int</span> data;
    <span class="hljs-keyword">struct</span> node* next;
};

<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> node Node;

Node *head = NULL;

Node* traverseTail (Node* np) {
    <span class="hljs-keyword">if</span> (np == NULL)        <span class="hljs-comment">// TERMINAL CONDITION_1</span>
        <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    <span class="hljs-keyword">if</span> (np-&gt;next == NULL)  <span class="hljs-comment">// TERMINAL CONDITION_2</span>
        <span class="hljs-keyword">return</span> np;

    <span class="hljs-keyword">return</span> traverseTail (np-&gt;next);
}

<span class="hljs-keyword">int</span> traverseSum (Node* np, <span class="hljs-keyword">int</span> i) {

    <span class="hljs-keyword">if</span> (np == NULL)    <span class="hljs-comment">// TERMINAL CONDITION</span>
        <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;

    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"node %d: %d\n"</span>, i++, np-&gt;data);
    <span class="hljs-keyword">return</span> np-&gt;data + traverseSum(np-&gt;next, i);
}

Node* createNode (<span class="hljs-keyword">int</span> val) {
    Node* n = (Node*) <span class="hljs-built_in">malloc</span> (<span class="hljs-keyword">sizeof</span> (<span class="hljs-keyword">struct</span> node));
    n-&gt;data = val;
    n-&gt;next = NULL;

    <span class="hljs-keyword">return</span> n;
}

<span class="hljs-keyword">int</span> main () {

    <span class="hljs-keyword">int</span> numbers[<span class="hljs-number">8</span>] = {<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">4</span>, <span class="hljs-number">5</span>, <span class="hljs-number">6</span>, <span class="hljs-number">7</span>, <span class="hljs-number">8</span>};

    <span class="hljs-comment">// forming the linked list</span>
    Node* head = (Node*)<span class="hljs-built_in">malloc</span> (<span class="hljs-keyword">sizeof</span>(<span class="hljs-keyword">struct</span> node));
    Node* np = head;

    <span class="hljs-keyword">int</span> i;
    <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i&lt; <span class="hljs-number">8</span>;i++, np = np-&gt;next) {
        np-&gt;next = createNode(numbers[i]);
    }

    <span class="hljs-keyword">int</span> res = traverseSum (head-&gt;next, <span class="hljs-number">0</span>);
    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"Sum of the elements in list %d\n"</span>, res);

    res = traverseTail(head)-&gt;data;
    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"Tail data is %d\n"</span>, res);

    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;

}</code></pre>


<h4 id="output-3">Output</h4>


<pre class="prettyprint"><code class=" hljs applescript">node <span class="hljs-number">0</span>: <span class="hljs-number">1</span>
node <span class="hljs-number">1</span>: <span class="hljs-number">2</span>
node <span class="hljs-number">2</span>: <span class="hljs-number">3</span>
node <span class="hljs-number">3</span>: <span class="hljs-number">4</span>
node <span class="hljs-number">4</span>: <span class="hljs-number">5</span>
node <span class="hljs-number">5</span>: <span class="hljs-number">6</span>
node <span class="hljs-number">6</span>: <span class="hljs-number">7</span>
node <span class="hljs-number">7</span>: <span class="hljs-number">8</span>
Sum <span class="hljs-keyword">of</span> <span class="hljs-keyword">the</span> elements <span class="hljs-keyword">in</span> <span class="hljs-type">list</span> <span class="hljs-number">36</span>
Tail data <span class="hljs-keyword">is</span> <span class="hljs-number">8</span></code></pre>


<h3 id="alternative-fibonacci">Alternative Fibonacci</h3>


<pre class="prettyprint"><code class="language-c hljs "><span class="hljs-preprocessor">#include &lt;stdio.h&gt; </span>

<span class="hljs-keyword">int</span> generate_fibo (<span class="hljs-keyword">int</span> fibopp, <span class="hljs-keyword">int</span> fibop, <span class="hljs-keyword">int</span> count, <span class="hljs-keyword">int</span> slen) {

    <span class="hljs-keyword">int</span> fibo = fibopp + fibop;
    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"%d "</span>, fibo);

    <span class="hljs-keyword">if</span> (count == slen) {   <span class="hljs-comment">// TERMINAL CONDITION</span>
        <span class="hljs-keyword">return</span> fibo;       <span class="hljs-comment">// for the nth Fibonacci number</span>
    }

    <span class="hljs-comment">// prepare to generate the next in sequence</span>
    fibopp   = fibop;
    fibop    = fibo;
    <span class="hljs-keyword">return</span> generate_fibo (fibopp, fibop, count+<span class="hljs-number">1</span>, slen);
}

main (<span class="hljs-keyword">int</span> argc, <span class="hljs-keyword">char</span>** argv) {

    <span class="hljs-keyword">int</span> seq_length = atoi (argv[<span class="hljs-number">1</span>]);
    <span class="hljs-keyword">if</span> (seq_length &lt;= <span class="hljs-number">2</span>) <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;

    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"The fibonacci sequence (%d) is "</span>, seq_length);

    <span class="hljs-keyword">int</span> fibo1 = <span class="hljs-number">0</span>, fibo2 = <span class="hljs-number">1</span>;
    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"%d %d "</span>, fibo1, fibo2);
    <span class="hljs-keyword">int</span> fibFinal = generate_fibo (fibo1, fibo2, <span class="hljs-number">3</span>, seq_length);

    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"\nThe %d in fibonacci sequence is %d\n"</span>, seq_length, fibFinal);

    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}
</code></pre>


<h4 id="output-4">Output</h4>


<pre class="prettyprint"><code class=" hljs vhdl">The fibonacci <span class="hljs-keyword">sequence</span> (<span class="hljs-number">13</span>) <span class="hljs-keyword">is</span> <span class="hljs-number">0</span> <span class="hljs-number">1</span> <span class="hljs-number">1</span> <span class="hljs-number">2</span> <span class="hljs-number">3</span> <span class="hljs-number">5</span> <span class="hljs-number">8</span> <span class="hljs-number">13</span> <span class="hljs-number">21</span> <span class="hljs-number">34</span> <span class="hljs-number">55</span> <span class="hljs-number">89</span> <span class="hljs-number">144</span>
The <span class="hljs-number">13</span> <span class="hljs-keyword">in</span> fibonacci <span class="hljs-keyword">sequence</span> <span class="hljs-keyword">is</span> <span class="hljs-number">144</span>
</code></pre>


<h3 id="recursive-halfof">Recursive HalfOf</h3>


<h4 id="httpjmphalfofreckg-1"><a href="http://j.mp/halfOfRecKG">http://j.mp/halfOfRecKG</a></h4>


<pre class="prettyprint"><code class=" hljs cpp"><span class="hljs-preprocessor">#include &lt;stdio.h&gt; </span>

<span class="hljs-keyword">void</span> halfOf (<span class="hljs-keyword">int</span> val) {

    <span class="hljs-keyword">if</span> (val == <span class="hljs-number">0</span>)          <span class="hljs-comment">// #1 TERMINAL CONDITION</span>
        <span class="hljs-keyword">return</span>;

    <span class="hljs-built_in">printf</span> (<span class="hljs-string">"%d "</span>, val);   <span class="hljs-comment">// #2 Do something </span>
    halfOf (val/<span class="hljs-number">2</span>); <span class="hljs-comment">// #3 Make the recursive call    </span>
}

<span class="hljs-keyword">int</span> main ()
{
    <span class="hljs-keyword">int</span> start = <span class="hljs-number">21</span>;
    halfOf (<span class="hljs-number">21</span>);
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}</code></pre>

<p>To visualize this code, click <a href="http://j.mp/halfOfV">http://j.mp/halfOfV</a></p>

<iframe width="800" height="500" src="http://pythontutor.com/iframe-embed.html#code=%23include%20%3Cstdio.h%3E%20%0A%0Avoid%20halfOf%20(int%20val%29%20%7B%20%0A%0A%20%20%20%20if%20(val%20%3D%3D%200%29%20%0A%20%20%20%20%20%20%20%20return%3B%20%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20printf%20(%22%25d%20%22,%20val%29%3B%20%0A%20%20%20%20return%20halfOf%20(val/2%29%3B%0A%20%20%20%20%0A%7D%0A%0Aint%20main%20(%29%20%0A%7B%0A%20%20%20%20int%20start%20%3D%2021%3B%0A%20%20%20%20%0A%20%20%20%20halfOf%20(21%29%3B%20%0A%20%20%20%20%0A%20%20%20%20return%200%3B%0A%0A%7D&amp;codeDivHeight=400&amp;codeDivWidth=350&amp;curInstr=10&amp;origin=opt-frontend.js&amp;py=c&amp;rawInputLstJSON=%5B%5D"> </iframe>


<h3 id="tower-of-hanoi">Tower of Hanoi</h3>


<h4 id="httpjmptowerofhanoicc"><a href="http://j.mp/towerOfHanoiCC">http://j.mp/towerOfHanoiCC</a></h4>


<h3 id="right-numeric-triangle">Right Numeric Triangle</h3>


<h4 id="httpjmprecrighttriangle"><a href="http://j.mp/recRightTriangle">http://j.mp/recRightTriangle</a></h4>


<h3 id="recursive-sorts">Recursive Sorts</h3>


<h4 id="selection-sort">Selection Sort</h4>


<h5 id="httpjmpselectionsortcc"><a href="http://j.mp/selectionSortCC">http://j.mp/selectionSortCC</a></h5>


<pre class="prettyprint"><code class="language-python hljs "><span class="hljs-comment"># https://code.activestate.com/recipes/576917-functional-selection-sort/#c1 </span>

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">selectsortr</span><span class="hljs-params">(l)</span>:</span>
    <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> l: <span class="hljs-keyword">return</span> []
    idx, v = min(enumerate(l), key=operator.itemgetter(<span class="hljs-number">1</span>))
    print(v, l[:idx], l[idx+<span class="hljs-number">1</span>:])
    <span class="hljs-keyword">return</span> [v] + selectsortr(l[:idx] + l[idx + <span class="hljs-number">1</span>:])

<span class="hljs-keyword">or</span>

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">selectsortr</span><span class="hljs-params">(L)</span>:</span>
    <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> L: <span class="hljs-keyword">return</span> []
    smallest = min(L)
    L.remove(smallest)
    <span class="hljs-keyword">return</span> [smallest] + selectsortr(L)</code></pre>

<h4 id="insertion-sort">Insertion Sort</h4>


<h5 id="httpjmpinsertionsortcc"><a href="http://j.mp/insertionSortCC">http://j.mp/insertionSortCC</a></h5>


<pre class="prettyprint"><code class="language-python hljs ">
<span class="hljs-keyword">import</span> bisect

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">insertion_sort</span><span class="hljs-params">(l, nsorted=<span class="hljs-number">1</span>)</span>:</span>
    <span class="hljs-keyword">if</span> nsorted &gt;= len(l):
        <span class="hljs-keyword">return</span> l
    bisect.insort(l, l.pop(), hi=nsorted)
    <span class="hljs-keyword">return</span> insertion_sort(l, nsorted + <span class="hljs-number">1</span>)</code></pre>


<h4 id="merge-sort">Merge Sort</h4>


<pre class="prettyprint"><code class="language-python hljs "><span class="hljs-keyword">from</span> heapq <span class="hljs-keyword">import</span> merge

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">mergesort</span><span class="hljs-params">(w)</span>:</span>
    <span class="hljs-keyword">if</span> len(w)&lt;<span class="hljs-number">2</span>:
        <span class="hljs-keyword">return</span> w
    <span class="hljs-keyword">else</span>:
        mid = len(w) // <span class="hljs-number">2</span>
        <span class="hljs-keyword">return</span> merge(mergesort(w[:mid]), mergesort(w[mid:]))</code></pre>


<h4 id="quick-sort">Quick Sort</h4>


<pre class="prettyprint"><code class="language-python hljs "><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">quicksort</span><span class="hljs-params">(s)</span>:</span>
  len_s = len(s)
  <span class="hljs-keyword">if</span> len_s &lt; <span class="hljs-number">2</span>:
    <span class="hljs-keyword">return</span> s

  pivot = s[random.randrange(<span class="hljs-number">0</span>, len_s)]

  L = [x <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> s <span class="hljs-keyword">if</span> x &lt; pivot]
  E = [x <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> s <span class="hljs-keyword">if</span> x == pivot]
  G = [x <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> s <span class="hljs-keyword">if</span> x &gt; pivot]

  <span class="hljs-keyword">return</span> quicksort(L) + E + quicksort(G)
</code></pre>

<p><strong>Javascript alternative for selectsort</strong></p>

<pre class="prettyprint"><code class="language-javascript hljs "><span class="hljs-comment">// helper function that returns the index of the</span>
<span class="hljs-comment">// minimum value in the array </span>
<span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">indexOfMinValue</span><span class="hljs-params">(arr)</span>{</span>
    <span class="hljs-keyword">return</span> arr.reduce((iMin, x, i) =&gt; x &gt; arr[iMin]? iMin : i, -<span class="hljs-number">1</span>);
}
<span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">selectSortR</span><span class="hljs-params">(a)</span>{</span>
  <span class="hljs-keyword">if</span> (!a.length) <span class="hljs-keyword">return</span> [];                     <span class="hljs-comment">// #1</span>
  <span class="hljs-keyword">let</span> minVal = a.splice(indexOfMinValue(a), <span class="hljs-number">1</span>); <span class="hljs-comment">// #2 and #3 </span>
  <span class="hljs-keyword">return</span> [minVal].concat(selectSortR(a));       <span class="hljs-comment">// #4 and #5</span>
}</code></pre>