Thoughts on recursive algorithms

I have always intuitively shied away from using recursion in my code wherever possible. The few times I have had to implement it were mainly in some form of tree traversal logic. I am a little uncomfortable in relying on intuition, so in this post I’m going to flesh out my thoughts on recursion. 

In certain scenarios a recursive implementation is very concise. Let’s take a look at a recursive Merge Sort:

void mergeSort(std::vector<int>&amp; a, int l, int r) 
{ 
    if (l < r) 
    { 
        int m = (l+r)/2; 
  
        mergeSort(a, l, m); 
        mergeSort(a, m+1, r); 
  
        merge(a, l, m, r); 
    } 
} 

This is very concise but the recursive logic calls are difficult to follow. The best representation of this I’ve found is this from geeksforgeeks.com:


From: https://www.geeksforgeeks.org/merge-sort/

This is quite elegant how the numbers get split up through the recursive calls and then get merged as the recursive calls unwind. It is however not intuitive by looking at the source code and requires some thought, thinking through the recursive call tree. The other disadvantage is the inherent limitations of recursive calls, i.e. the overhead of the recursive calls and stack size limit which limits the scalability for large data sets.

Lets compare this to an iterative implementation:

void merge_sort_iterative(std::vector<int>&amp; nums) {
	int chunk_size = 1; //start merging one element at a time
	for ( ; chunk_size <= nums.size()-1; chunk_size*=2) {
		//iterate through this pass merging adjacent chunks
		for (int idx=0; idx<nums.size(); idx+=(chunk_size*2)) {
			int merge_size = chunk_size*2;
			if (nums.size()-idx < merge_size)
				merge_size = nums.size()-idx;
			if (merge_size==1)
				continue;
			merge_sort_combine(nums, idx, chunk_size);
		}
	}
}

I’ve used more descriptive variable names and comments here, so the comparison is not completely fair. Both the recursive and iterative solutions rely on a merge function not shown, but these would have similar logic. The key difference is that the iterative is intuitively easier to understand as you don’t have to think through the recursive call tree.

It is interesting that most descriptions of merge sort default to a recursive implementation. I would argue that the iterative solution is easier to understand and implement. The recursive solution is an interesting learning exercise in the way the recursive call tree unravels.

In some cases implementing an iterative alternative to a recursive algorithm requires using a stack data structure. An example is an iterative version of a quick sort, which repeatedly pushes the two partition dimensions to a stack and then repeatedly pops elements off the stack and does a partition again:

void quicksort_iterative(std::vector<int>&amp; nums, int l, int r) {
	std::stack<std::pair<int,int>> s;
	s.push({l,r});

	while (s.size() > 0) {	
		auto bounds = s.top();
		s.pop();
		int cur_l = bounds.first;
		int cur_r = bounds.second;
		if (cur_r-cur_l >= 1) {
			int i = partition(nums, cur_l, cur_r);
			s.push({cur_l,i-1});
			s.push({i+1,cur_r});
		}
	}
}

So to summarise I would say recursive implementations, compared to iterative alternatives, tend to be:
– less intuitive
– less efficient
– less scalable

Posted in programming | Tagged , | Leave a comment

Thoughts on the software development process

I’m going to talk about some reading material and my own ideas on the software development process:

“Hackers and Painters” by Paul Graham

http://www.paulgraham.com/hp.html

This is a great essay in which Paul Graham sees hackers as having more in common with painters than mathematicians and scientists in the field of Computer Science. He extols the practice of tinkering and making rather than rigidly formally designing everything ahead of any code writing. He also talks about big companies often crushing hacker creativity through designing by committee and layers of product managers that ends up with mediocre software. 

Creative Selection by Ken Kocienda

In his book Creative Selection, Ken Kocienda describes a software development process that seems compatible with the hacker ethic. The book focuses on the latter years of Steve Jobs’ time at Apple, and in particular during the early iPhone development. Ken describes a system of Directly Responsible Individuals (DRIs) that were responsible for particular pieces of functionality. Steve Jobs, the Apple CEO, would talk directly to the DRI of features and their opinions would be most important. There was a remarkably thin hierarchy and no product managers. At that early stage, there were about 8 software engineers that would be paired up with designers. Above that there was a manager that oversaw the software engineers and a manager that oversaw the designers. And then above that there was Steve Jobs. The development process involved a lot of prototyping and frequent demos. I’ve seen a few interviews with Ken but this is my favourite:

Andreessen-Horowitz page for the interview:
https://a16z.com/2019/02/24/apple-steve-jobs-software-product-design-process-ken-kocienda-creative-selection/
Book website: http://creativeselection.io/

Facebook mobile development

Facebook, not surprisingly given their original motto of “move fast and break things”, have a very agile development process:
https://www.androidauthority.com/facebook-mobile-app-development-process-965204/

“… everyone can work on what’s most pressing for them all the time, and that every other part of the business knows what they are doing. There’s a high level of ownership for each engineer, and everyone is ultimately responsible for their own work. Not only does this make the company more agile, but it also hopefully increases workplace satisfaction. No one is just a cog in the machine.”

“… anyone from anywhere within the organization could suggest an idea for a new feature, and then get to work on that if given the go-ahead. Sometimes this might even develop into its own separate app! Facebook is much more a collaborative project than the top down enforced vision of a few people (or one person) it is often portrayed as.”

My own thoughts

My own personal angle on this, which I don’t see getting talked about a lot, is related to the effects of having developers being passionate about their software and loving what they do. In my experience this makes all the difference. When a developer is passionate about their software, they will put more effort on the little details that turns good software into great software. Obviously there needs to be the correct environment to cultivate this passion for the work. In my opinion good software development requires dedicating large blocks of time without distraction to get in “the zone” where productivity is high. In my experience, most individuals that reach an elite level in their field (be it software development, entrepreneurism, science, sports or anything) have an almost obsessive mindset where the pursuit of their goals consumes their life.  

Regarding the DRI concept, I will add that leadership is important for a software developer. Not necessarily leadership as in managing other people but leadership as in taking responsibility for your area of code/functionality and using initiative to be proactive in the evolution of that area. 

Posted in technology | Tagged , | Leave a comment

xdiffr initial release

I have rewritten my differencing application to be cross platform. I have rebranded it to xdiffr and I have made it open source. You can download built Windows and Linux executables here:
https://adamk.org/xdiffr
The source code is hosted on github:
https://github.com/adamkorg/xdiffr

You are more than welcome to download and play around with the source code. I will try to merge in any contributed changes that have broad appeal.

Information about the old Windows only application can still be found here:
https://adamk.org/xdiff

Posted in technology | Tagged , | Leave a comment

Google+

This site seems to be swamped with spam comments, so I’m sorry if I’ve missed some genuine ones amongst them. There are about 200 pending for me to check.

I have been posting mainly to Google+ recently. Check me out on there:
https://plus.google.com/u/0/108986466058109956412/posts
or the shortened url:
http://plus.ly/adamk

Posted in Uncategorized | Leave a comment

International Space Station flyovers

I finally got to see the ISS fly overhead last night. This inspired me to create some infographics for some perspective on the distances of satellites.

To find out a schedule of when the ISS flies over your area:
http://www.heavens-above.com/
A map that tracks the current position of the ISS:
http://www.n2yo.com/?s=25544

Posted in Uncategorized | Leave a comment

Freezing hard drive as last resort data recovery

In the last few years I’ve had two hard drives fail. As a last resort each time I put the drive in a freezer for about half a day and then managed to recover most of the data.

WARNING: If the data on the failed hard drive is very valuable to you then get professional data recovery advice. I tried numerous software recovery tools and none of them worked. I was not prepared to pay out for physical hard disk recovery, so I decided to try freezing.

On the most recent HDD failure I noticed that it made a clicking noise. The PC displayed a “no operating system found” message and the drive was inaccessible on other PCs. First I tried putting the drive in a freezer for a couple of hours but this did not work. I then left it in the freezer for about 14 hours and then it worked. Note that if this works there will probably be a limited time in which you will be able to use the drive, so copy the most important data first. The first time I had long enough to copy the entire drive but the second time I only managed the get about half of the data. Don’t forget to put the drive in a plastic bag or two before putting it in the freezer.

It seems that science behind this is that the components in the drive shrink slightly when cold. This tightens up mechanical parts that might have become loose and could improve electrical contact issues.
http://server.dzone.com/news/what-do-when-hard-drive-fails

Not wanting to push my luck too far, I am now using RAID mirroring with two hard drives!

Posted in technology | Tagged , | 2 Comments

adamk.org blog header image

The current header image for this blog is based on the “Earth and Sun” photo from NASA:

The Setting of the Sun Over the Pacific Ocean and a Towering Thundercloud, July 21, 2003 As Seen From the International Space Station (Expedition 7); Image Science and Analysis Laboratory, NASA-Johnson Space Center. “Astronaut Photography of Earth – Display Record.”

http://sunearthday.nasa.gov/2008/promotional/index.php

Posted in science | Tagged , | Leave a comment

Docbook introduction

Docbook is a specification for writing documentation in XML*. Once an XML document containing the data content of the documentation has been created, it can be processed by XSL transforms to produce an output format (pdf, html, chm and more…). This proved particularly useful for a project at work, where I generated a set of output formats from a single XML data source.

Tools, examples and resources after the jump.

Continue reading

Posted in technology | Tagged , | 1 Comment

Zombie ants controlled by parasite fungus

The Ophiocordyceps unilateralis fungus infects carpenter ants and then somehow makes the ant move to a leaf at a specific height (out of the ant’s normal habitat). The ant will then clamp on to the underside of the leaf and will then die. The fungus then erupts a long stalk out of the ant’s head. This then sprinkles spores that can infect more ants and the cycle starts again.

Credit to Carl Zimmer and Brian Mallow, who talked about this on episode 89 of Dr Kiki’s Science hour:
http://twit.tv/dksh89
In this episode they also talk about the crustacean parasite Cymothoa exigua, which replaces a fishes tongue. Read about this and other disgusting parasites here:
http://www.livescience.com/13040-10-disgusting-parasites-zombie-ants-toxoplasma.html

One last interesting fact: The human body carries around 10 times more bacteria cells than our own body cells. However, the bacteria cells are much smaller than our own cells. Without these bacteria, we would be in big trouble.
http://www.wired.com/medtech/health/news/2004/10/65252

Posted in science | Tagged , | 2 Comments

The Universe in numbers

The total number of stars in the universe is greater than all the grains of sand on all the beaches on earth.

10,000 grains of sand in a handful of sand, which is roughly the same as:
10,000 stars visible in the sky on a clear night.

100,000,000,000 (100 billion) stars in an average galaxy.
100,000,000,000 (100 billion) galaxies in the universe.

These numbers are from Carl Sagan’s Cosmos TV Series. Here’s a clip from it:
http://www.wimp.com/starssand/
I’ve ordered the complete DVD set from Amazon:

Posted in science | Tagged | Leave a comment