Category: Programming Tools & Languages

Recursion / Recursive Functions

Recursion / Recursive Functions

[Image by Maurits Cornelis Escher]

A recursive function is a function which calls itself.

It sounds like a simple concept, but in practice it can be hard to get your head around.

Here’s a lovely example of a recursive function:

void ExplainRecursion () {  
    var explained = GetInput(“Do you understand recursion yet?”);  
    if (!explained) {    
        ExplainRecursion();  
    }
}

It’s particularly nice because it uses recursion to explain recursion. It calls itself – it’s a recursive function. Every time it calls itself, it asks the question “Has recursion been explained yet?” and if the answer is No it calls itself again. It keeps calling itself repeatedly until recursion is finally understood, at which point it quits. What might not be immediately obvious is that when it quits, it will still be inside the previous call, and will keep returning until it reaches the first time it was called. Like this:

ExplainRecursion()

—–>Do you understand recursion yet?

—–>No => ExplainRecursion()

———->Do you understand recursion yet?

———->No => ExplainRecursion()

—————>Do you understand recursion yet?

—————>No => ExplainRecursion()

——————–>Do you understand recursion yet?

——————–>Yes! => Exit function

—————>Exit function

———->Exit function

—–>Exit function

Exit function

It’s true that this is a slightly jokey example. It works if you see the source code, but if you only ever saw the output you wouldn’t learn much about recursion. You’d just be asked the same question repeatedly and probably get a bit angry.

Here’s another simple example:

void Factorial(int n) {
    if (n == 1) {
        return 1;
    } else {
        return n * Factorial(n-1);
    }
}

This function is calculating “n factorial”, which is written as “n!” in mathematical notation. In case you’ve forgotten or haven’t come across this concept before, it’s easiest to explain with a concrete example: 5! (“five factorial”) is a quick way of writing 5 x 4 x 3 x 2 x 1. So n! means take the number n and multiply it by all the whole positive numbers that lie between itself and zero.

The above function calls itself, which means that unless n is 1 (because 1 factorial just equals 1), it will return a result… to itself.

Don’t worry if you’re feeling lost already. It took me a long time to be able to look at recursive functions without getting an instant headache. I found it helpful to draw little diagrams. For instance, if we use the above function to calculate 5 factorial.

Remember, the answer we expect is 5 x 4 x 3 x 2 x 1.

The first time we enter the function, we call Factorial(5), so n = 5. The function returns 5 x Factorial(4), so it gets called again and this time n = 4. That returns 4 x Factorial(3), which returns 3 x Factorial(2), which returns 2 x Factorial(1). Factorial(1) just returns 1. Here’s a diagram to help:

Factorial(5) = 5 x Factorial(4)

—–>Factorial(4) = 4 x Factorial(3)

———->Factorial(3) = 3 x Factorial(2)

—————>Factorial(2) = 2 x Factorial(1)

——————–>Factorial(1) = 1

—————>= 2 x 1

———->= 3 x (2 x 1)

—–>= 4 x (3 x (2 x 1))

= 5 x (4 x (3 x (2 x 1)))

Normally when a function returns a value, it’s over. We can move on. But with a recursive function, we might just land back inside ourselves again, and then we might return a value to yet another version of ourselves. With complex functions, this can be hard to trace through in your head without losing track. It’s also horribly easy to get stuck in an infinite loop.

Hopefully this helped. If not, don’t worry. It’s not just you! It’s a notoriously head-twisty concept.

 

What to do when you get stuck in a Vim editor

Anybody using Git straight out of the box on the command line is likely to have found themselves suddenly stuck in a Vim editor. If you’re not used to Vim, this can be a highly discombobulating experience. Here’s how to escape!

  • Quick Guide:
    • Type i to get into insert mode
      • (no need for colon)
      • (if it’s worked, you’ll see “– INSERT –” at bottom of screen
    • Type your commit message
    • Click Esc
    • Type :wq to save and quit
      • Or type :q! to quit without saving
    • Hit Enter

Changing your Default Git Editor

  • You don’t have to have Vim as your default editor! You can change to an editor of your choice (eg Notepad)
  • Note that these instructions were written for Windows. I don’t know about other operating systems but I’m guessing it’ll be similar
    • Find and open your .gitconfig file
      • (probably here: C:\Users\[user-name])
    • Add this section to the bottom:
      • [core]
      • editor = ‘C:/Program Files (x86)/Notepad++/notepad++.exe’
    • Save and close the file.
    • When you’re committing with git, just write git commit and press Enter. It will pop open Notepad++.
    • Write your commit message at the top of the file, and save and close the file. Done!
      • …but it doesn’t always work like that, in which case you might have to go back to VIM and just learn the VIM basics
  • More here: http://stackoverflow.com/questions/2596805/how-do-i-make-git-use-the-editor-of-my-choice-for-commits

Searching and search / replace in Vim

(Note that this was written after I spent a few months learning Vim. If you’re just stuck in Vim and want to get out, see What to do when you get stuck in a Vim editor).

I’m publishing my notes on the things that are useful in Vim but that I keep forgetting. My notes are split into four sections, so I’ll publish four posts:

This is the fourth post, and it’s about searching  and search / replace in Vim.

Search for term in file

  • Like this: /[search term – regex]
  • Type n to get next search result
  • Type N to get previous search result
  • For case insensitive search, add \c to the command (either at start or end)
  • If you then get highlighting which won’t go away, type :noh

Search and replace

  • Like this: :%s/[search term]/[replacement]/g
    • %s means whole file, /g means every occurrence on every line
    • If you want it to ask you for confirmation on every replacement, add c as well: :%s/foo/bar/gc
    • More here: https://vim.fandom.com/wiki/Search_and_replace
    • And here: https://www.linux.com/learn/vim-tips-basics-search-and-replace
    • If your strings contain forward slashes, then you can replace the forward slashes in the command with any other character!
    • For case insensitive search, add \c to the command (either at start or end)
    • To do it on whole words only: :%s/\<word\>/newword/g – you have to delimit the word with \< and \>

Find character on this line

  • f – find character on this line
    • Add a number to do multiple
    • Eg 2f_ will find the second underscore character on this line

Find the word under the cursor

  • This: *
    • This works on words containing underscores
    • By default it won’t work on words containing hyphens
      • You can change this by adding set iskeyword+=- to .vimrc
      • Or just type :set isk+=- in Vim

Find whatever text you have highlighted (in visual mode)

Navigating files, lines and blocks in Vim

(Note that this was written after I spent a few months learning Vim. If you’re just stuck in Vim and want to get out, see What to do when you get stuck in a Vim editor).

I’m publishing my notes on the things that are useful in Vim but that I keep forgetting. My notes are split into four sections, so I’ll publish four posts:

This is the third post, and it’s about navigating files, lines and blocks in Vim.

Navigating lines

Navigating files

  • Go to top of file: gg
  • Go to end of file: shift + g
  • Go to line number: line-number + shift + g
  • Navigation within chars / lines: j = down, k = up, h = left, l = right

Navigating blocks delineated by {}, (), [], <> or “”

  • The diff between % and [{ always confuses me cos it’s not explained well in Vim Adventures:
    • % will take you to the matching bracket if you are already ON a bracket. It only works on {}, () and [] (not <>)
    • [{ will search backwards for the enclosing { if you are already IN a {} block – so it takes you to the start of your current scope
      • ]} will move forwards and take you to the end of your current scope
      • ]{ is meaningless (I think)
      • [( and )] will also work in the same way
      • [< does not work, [“ does not work, and [[ does something totally different
      • If you want to move back to blocks that enclose your current block, use numbers
        • So for instance, 3[{ will take you to the beginning of this snippet of code if your cursor is in the innermost scope:
        • {
          • {
            • {I am here}
          • }
        • }
      • In Vim Adventures type :help [{

If you want to navigate inside a block delineated by [], <> or “”

  • You can use % to find the matching brace if you are on [ or ] but not < or >
  • You can use visual mode to select the contents of {}, [], (), <> or “”
    • Use a to select the contents AND the delineators
    • Use i to select the inner contents (ie without the delineators)
    • Use the OPENING delineator to indicate what your scope is
    • These are all the possible commands: va{, vi{, va[, vi[, va(, vi(, va<, vi<, va”, vi”
    • If you want to select blocks that enclose your current block, use numbers
      • So for instance, v3a{ will select this whole snippet of code if your cursor is in the innermost scope:
      • {
        • {
          • {I am here}
        • }
      • }
    • Once you’re in visual mode you can use commands like i, p, c, a, s
    • In Vim Adventures type :help a{ or help i{
      • You can use c to select the contents of {}, [], (), <> or “” and then it will put you into Insert mode to replace what was there
        • Same principles as with v (see above)
        • These are all the possible commands: ca{, ci{, ca[, ci[, ca(, ci(, ca<, ci<, ca”, ci”
        • As with v you can use numbers to select multiple enclosing blocks (see above) but the number comes BEFORE c, like this: 3ca{
        • (There are others too, like caw and ciw for words – in Vim Adventures type :help aw and :help iw)

Vertical Columns in Vim (“visual blocks”)

(Note that this was written after I spent a few months learning Vim. If you’re just stuck in Vim and want to get out, see What to do when you get stuck in a Vim editor).

I’m publishing my notes on the things that are useful in Vim but that I keep forgetting. My notes are split into four sections, so I’ll publish four posts:

This is the second post, and it’s about vertical columns of text (“visual blocks”). It’s the same functionality that you get using alt + click in a lot of other text editors.

  • Ctrl + v takes you into “visual block” mode, then use the up and down arrows.
  • Commands like x will work instantly
  • But if you want to do something like substitute (s) or append (A only, a won’t work) or change (c), you need to execute the full command first – at which point it will look like it’s only worked on one line – and then press Esc twice – and finally your change will appear on multiple lines.
  • If you want to type replacement text, you use insert mode but it has to be I instead of i (upper case instead of lower case). As with s, a and c you won’t see the full effect until you exit Insert mode AND visual mode (press Esc twice).
  • To insert one vertical column of text in front of another one:
    • Go to the place you’re copying from
    • Use ctrl+v to go into visual block mode
    • Use y to copy the highlighted text
    • Go to your destination
    • Use ctrl+v to select a column of text consisting of the first character of the place you want your new column to go in front of
    • Use I to go into insert mode, and type one space
    • Press Esc, and you’ll see you have inserted a column of single spaces
    • Now use ctrl+v again to highlight the column of spaces
    • Use p to paste your original column selection
    • There is an explanation here for why you can’t do it without typing the extra space: https://stackoverflow.com/questions/31893732/vim-how-do-i-paste-a-column-of-text-from-clipboard-after-a-different-column-o

 

Miscellaneous Vim Stuff

Note that this was written after I spent a few months learning Vim. If you’re just stuck in Vim and want to get out, see What to do when you get stuck in a Vim editor.

This will be another notey one. Really I just want to stick this somewhere I can easily access it. I’m going to publish my notes on the things that are useful in Vim but that I keep forgetting. My notes are split into four sections, so I’ll publish four posts:

Before I get going though, a mildly funny anecdote: A colleague messaged me recently and mentioned that his vim had been upset by some house renovation work, and I wondered how said renovation could have such an impact on his command-line text editor…. before I realised that he meant vim as in “vim and vigour”.

OK, so here is some miscellaneous Vim stuff:

  • Vim cheat sheet – http://hamwaves.com/vim.tutorial/images/vim.en.png
  • Great online “Vim Adventures” game you can use to learn Vim: https://vim-adventures.com/
  • If you make changes to ~/.vimrc and want to reload:
    • Type :so $MYVIMRC
    • …but actually you can just type $MY and then tab to autocomplete.
  • Searching:
  • Navigating files, lines, blocks
  • Copy / paste:
    • Copy current line (“yank”): yy – which is the same as Y
    • Paste current line below the line you are on (“put”): p
    • To replace one line with another: Y to yank a line, then go to the line you want to replace and type Vp
      • V puts the whole line into visual mode, and then p pastes the register into the visual selection (the whole line).
  • Append, Substitute and Change
    • Append is a to append after current character or A to append at end of line
      • (puts you into insert mode)
    • Substitute is s to substitute current character and S to substitute current line
      • (puts you into insert mode)
    • Change is c to replace whatever you specify – eg aw for a word, iw for inner word (word without leading space)
      • (puts you into insert mode)
      • C is to replace from cursor to end of line
      • See also separate section below on navigating blocks
  • Replace current word with contents of register: viwp
    • v is visual mode
    • iw is inner word
    • p is put
    • You might want to explicitly use the “0 register (like this: viw”0p), otherwise what’s in the default register might get replaced and if you try to repeat the action you get unexpected results
      • But for this to work, you will have to have used “0y (or whatever) first, to get your text into the correct register
  • Select a vertical column of text (like alt click)
  • Text objects:
  • To see line numbers: :set number
    • To make that change (or any other change) permanent:
      • Cmd: vim ~/.vimrc
      • Type the line :set number into the file
      • It will take effect immediately
    • To turn line numbers off temporarily (for copy/pasting): :se nonu (then :se number to turn them back on again)
  • Do one command while in Insert mode, then return to Insert mode: Ctrl + o
    • This takes you to normal mode for one command
  • Most commands in vim take a function and then an argument
    • Eg j is a movement argument – so dj is the delete command with a “down” argument
    • Commonly repeat the function if there is no argument – so dd means just delete
  • u – undo
  • Ctrl + r – Redo
  • o – insert new line below (O = above)
    • Note this will also put you in insert mode
  • Tab (indent) left or right: < and > – eg << to just tab left
    • To indent a whole block: Use v to go into visual mode, then up and down keys to select lines, then < and > to indent in or out
  • Select an entire function definition
  • Set to use spaces instead of tabs
    • Cmd: :set expandtab ts=2 sw=2
    • ts = tabstop
      • Note this means that you can use the tab command and it will automatically insert 2 spaces
      • It also defines how he file will be displayed if it contains tab characters
    • sw = Shiftwidth
      • Something to do with what happens when you press enter, – automatic indentations?
  • Multiples
    • Add number at start
    • Eg 2f_ – find the second instance of underscore on this line
  • Delete characters – x for the char in front, X for the char behind (like backspace)
  • d – delete line
    • dd – delete current line
    • 4dd – delete 4 lines
    • dG – Delete all lines from current line to end of file
    • Shift+d – delete to end of line
    • Shift+c – delete to end of line and go into insert mode
    • dw – delete a word
  • J to join text that’s split across lines to turn it into one long string
    • Eg This…
      • Hey
        • Hello
          • You
        • And also
      • Goodbye
    • … becomes this:
      • Hey Hello You And also Goodbye
Paired Programming: Useful Articles, Resources and Research

Paired Programming: Useful Articles, Resources and Research

During my talk at NDC London this week, I promised to publish a list of resources you can use if you are trying to persuade people of the efficacy of paired programming as a software development technique. Here it is!

(incidentally, the image is of Sal Freudenberg and me doing some remote pairing – we use Zoom and we find it works really well – I often forget we are not in the same room).

Martin Fowler webinar, new Refactoring book

Martin Fowler webinar, new Refactoring book

These may well be the notiest notes I’ve ever published, but just in case they’re of any use to anyone… if nothing else they may whet your appetite for the new edition of Martin Fowler’s Refactoring book.

I confess I never read it first time round (not on purpose, just there are so many books in the world and so little time…), so I’m looking forward to reading it this time. It hasn’t come out yet in the UK but should be some time in the next few weeks. Mine is already on order [drums fingers impatiently].

So anyway, Martin did a webinar today on the topic of his new book, and here are my notes:

Refactoring should be done via small changes

  • v small semantics-preserving changes
  • So small they’re not worth doing on their own
  • String together small changes to make a big change

When adding new functionality:

  • Alternate between refactoring and adding functionality
  • Often it’s easier to add new functionality if you refactor first
  • Balance between adding new functionality and refactoring – it’s a matter of judgement

V1 of Martin’s Refactoring book vs v2

  • Some things that were included in the first book he decided not to include I the second
    • Eg Unidirectional vs bidirectional – not important
  • Some things he thought were too trivial for the first book, he has now changed his mind about and included
    • Eg moving statements within a function
  • Most notable changes = no longer centrally object-oriented
    • “Extract function” used throughout instead of extract method
    • One of the refactorings is around the choice between OO and non-OO
    • The most visible thing here is the choice of language (javascript)
    • But language is not necessarily relevant anyway
  • OO vs functional
    • He doesn’t see that as a huge shift
    • OO should still have functional elements – referentially transparent
    • They are overlapping paradigms, not distinct

Favourite refactorings?

  • “Split phase”
    • Hunk of computation which can sensibly be divided into two phases with a data structure communicating between them
    • Eg parsing – separate the tokenising out – deal with a series of tokens instead of a stream of text
    • But if you split a loop, what if you are introducing performance problems? See below…

Performance and refactoring

  • Split loop is something people often worry about because it will run the loop through twice
  • Most of the time it doesn’t matter – a push for clarity will not change the performance of the code
  • Most of the time by refactoring you open up an opportunity for performance improvements you would never have noticed otherwise
  • Then again you should run performance tests frequently
  • Not necessarily with every build, but every day or two
  • But most micro-changes have no impact on performance
  • You will only find real performance impact by performance testing

Recommendations for other books?

Refactoring architecture:

  • Always have to ask, how do you make the smallest possible change?
  • Eg extracting a data-intensive microservice from a larger system
  • Most of the moves are happening within the monolith BEFORE you start firing up the external system
  • Then you move stuff in really small pieces
  • Things that change for similar reasons should be together – you need to see the relationship between them

Branching / trunk-based development

  • Develop on a branch and merge at the end, with branch being long-lived – days, weeks or months
    • Still a really common pattern
  • But if something has been refactored, you don’t find out until you merge – this can blow up on you
    • It means you become scared to refactor! There’s a disincentive.
  • Continuous integration: Integrate with each other fully at regular intervals – at least once a day
  • Every day you receive everyone else’s code changes and push your own changes back
  • Removes the big painful merge problem – not saving up for a big horrible crunch
  • Adage of Apollo – it hurts if you do it more often (?)
    • Sorry, I wrote this down but I’ve since Googled it and I don’t really know what it’s about – I may have misheard!
  • Open source development:
    • Actually this CAN be a good place to use branches, because everyone working separately and you can’t guarantee all changes should be merged
  • People call it trunk-based development but “continuous integration” is a better name because that’s what it’s really about
  • People worry about continuous integration but it’s less painful than they think
    • If you do integration every day it becomes easier and less painful until you stop even noticing

Responsibility

  • Keep code base in healthy state
  • If not you are stealing from colleagues, clients and employers!
  • But no point saying you should do it for moral reasons, that won’t motivate people to do it
  • It’s economic: Want to get more changes out more quickly
  • It’s professional: We’re being paid to produce features rapidly
  • It’s not up to managers or business: They don’t know how to keep code healthy – that’s what they pay us to do

Refactoring and design patterns – are they incompatible?

  • With a lot of patterns, you shouldn’t introduce them right away cos they’re not appropriate and you don’t require the full strength of them yet, particularly the more complicated ones
  • Introduce patterns as a result of refactoring: Refactor towards them
  • This was recognised by the original Design Patterns authors (Gamma, Helm, Johnson, Vlissides)
  • Also Josh Kerievsky: Refactoring to Patterns

Code smells

  • Code smell of the week!
    • “This week we will look at long methods” – whenever we find them we try to refactor them

When not to refactor!

  • Code that is never touched
    • Sitting behind an API, working quite happily, doesn’t need to change – doesn’t matter if it’s a mess!
  • Don’t clean code all in one go – just a little bit more every time you go in
    • Over time that will concentrate your efforts where they are most needed – ie areas modified most frequently

Refactor as a step in the red-green-refactor cycle

  • You should only refactor when tests are green
  • Sometimes that means you have to remove a failing test, refactor, then put the failing test back in again
  • Ralph Johnson, John Brant, Don Roberts wrote the first Smalltalk refactoring book (A refactoring tool for smalltalk?)

If you don’t have tests you can’t refactor?

  • “Probably safe” refactorings? Interesting route to go? Not a great thing for most people to focus on, requires a lot of expertise
  • For most people you should have tests as well – after all, how do you know whether you’re breaking what’s currently there?

Final takeaway:

  • Small steps, commit frequently.
  • Then you can always roll back.
Getting Started with .Net Core, ASP and WebAPI

Getting Started with .Net Core, ASP and WebAPI

I followed this tutorial, which is very good: https://docs.microsoft.com/en-us/aspnet/core/tutorials/web-api-vsc?view=aspnetcore-2.1

There were some gotchas though, so (as always) I made notes:

  • Whenever you add new code you have to stop running and rebuild before you can send successful requests.
  • When you do a POST, the port number is 5001 or 5000: It’s whatever you’re using in the browser for GET requests
  • When you add the Update method, you have to send another POST to create a new Todo item before you can update it. The url is the location field from the response of the POST.
  • When you add the Delete method, use the GET request in the browser to find the Ids of existing items so you know what you can delete. The url is the same as the Update url, with appropriate Id added on. Use the GET request to check whether deletes have worked. Use the POST to add elements you can then delete.
  • When you add a new database context you need to update the dependency injection stuff in Startup.cs and you need to make sure your POCO class has an Id property.

See also the following two posts: