Software Engineering Concepts: Recursion Tutorial

14 Launches
Solution Overview

There's a popular idiom in software engineering: in order to understand recursion, you must first understand recursion. This lab provides an environment for practicing writing recursive algorithms for a few challenging examples. Starting with a simple case of calculating the factorial of a number, you will be guided through the process of writing tests to define the behavior (Test-Driven Development or TDD) and then determine the base case and recursive step to solve the problem. You will progress to use what you have learned to solve the more challenging cases of calculating the Fibonacci sequence, and solving the "Tower of Hanoi" puzzle using recursive algorithms.

This lab uses the programming language TypeScript, so some familiarity with TypeScript or JavaScript (ECMA Script 2016) will be helpful to complete the lab. There are code samples throughout the documentation that will help you along, and checkpoints included for you to check out working code if necessary.

Goals & Objectives

Through this lab you will learn to:

  • Write unit tests to define the behavior of an algorithm.
  • Break a complicated problem into a simple case that can be applied recursively.
  • Compare between iterative and recursive approaches to a problem.
  • Calculate the factorial of a number using recursion.
  • Calculate the Fibonacci numbers using recursion.
  • Solve the Tower of Hanoi puzzle using recursion.

Hardware & Software

  • TypeScript
  • Node.js
  • Mocha
  • Chai
  • Babel