Skip to main content

Motivating Recursion (Sequencing Analysis)

note

This page provides an analysis of the sequencing principles used in the Motivating Recursion module. Find the module starting here.

Principles used:

  • General-to-specific: The concept of recursion is decomposed into four layers, with each layer providing more detail than the previous layer.

Recursion is a programming concept where a function calls itself. The concept is often difficult for new programmers to learn. Often, beginners are introduced to the subject through demonstration of a program that computes a factorial. While this is a good illustration of how recursion works, it is not a good example of when recursion should be used.

This tutorial takes a different approach. It presents a recursive example of traversing a directory tree, which is arguably more complex than the factorial example. However, it provides the learner with the motivation for using recursion. More importantly makes extensive use of the general-to-specific sequencing principle, where layers are used to simplify complexity.

The layers in this module are listed below. Layers 3a and 3b are on the same level. This is because the content in layer 3a does not help to further understand the content in layer 3b. Rather, the content in layer 3a is present to justify the use of recursion when using iteration is too complex.

  • Layer 1: The structure of a directory tree and an example
  • Layer 2: A starting point for implementing the directory tree traversal
  • Layer 3a: Iteratively traversing the directory tree
    • Layer 3a.1: Using a stack to store the directory entries to be processed
    • Layer 3a.2: Looking at the stack as each directory entry is processed
    • Layer 3b.3: The code
  • Layer 3b; Towards a recursive implmemention of the directory tree traversal
  • Layer 4: The recursive implemention of the directory tree traversal