Tag Archives: recursion

Convert an integer to a sequence of digits in Xquery

I am new to the functional programming paradigm and Xquery. As part of a larger exercise, I wanted to sum the digits of an integer.  The first part of that problem is to solve the smaller problem: convert an integer to a sequence of integers that I can then pass to fn:sum as a parameter.

(: I've declared the function in the nwnu namespace for testing purposes :)
declare function nwnu:number-to-seq($num as xs:integer)
as xs:integer* {
  if($num gt 9) then
    (
      nwnu:number-to-seq(xs:integer(math:floor($num div 10))),
      xs:integer(math:floor($num mod 10))
    )
  else
    $num
};

Read more »

Introduction to memoization with Javascript

Memoization is a function optimization technique used to avoid remaking calculations in subsequent function calls.  The classic example, which we’ll demonstrate here, is the factorial function.  5! = 5 * 4 * 3 * 2 * 1… factorials are recursive in nature if we give it some thought.  5! = 5 * 4! and 4! = 4 * 3! and so on.  By recognizing this pattern, we can also recognize that if we calculate 5! and save the results, then we should not have to recalculate it when we do 7!.  Instead of calculating 7! by 7 * 6 * 5 * 4 * 3 * 2 * 1, we’ll calculate it by 7 * 6 * 5!.

We’ll first examine the naive approach and then the memoization method.  All in Javascript, and all with code samples…
Read more »

Recursive Collatz conjecture in PHP

I stumbled across a blog post by Brie Gordon about the Collatz conjecture, so naturally I had to Wikipedia it. The simple story is that for any given integer, if it is even you divide it by 2 and if it is odd you multiply it by 3 and add 1. You continue this pattern with the returned numbers, and eventually the number will reach 1. So, to kill some time, I wrote a recursive version in PHP.  Here it is:

function collatz($num)
{   
  if($num == 1)
  {
    echo "<p style='color: red'>" . $num . "</p>\n";
    return;
  }

  if($num % 2 == 0) //even
  {
    echo "<p style='color: green'>" . $num . "</p>\n";
    return collatz($num / 2);
  }
  else
  {
    echo "<p style='color: red'>" . $num . "</p>\n";
    return collatz(3 * $num + 1);
  }
}