Learn How to Code
  • Welcome
  • Foundations
    • Introduction
      • Becoming a web developer
      • Motivation and mindset
      • Join a supportive community
      • How does the web work?
    • Requirements
      • Prerequisites
      • Text editors
      • Command line basics
      • Setting up Git
      • Setting up Node
    • Git
      • Git basics
      • Project: Practicing Git
    • Frontend
      • HTML and CSS
      • Developer Tools
      • Project: Create a web page
    • JavaScript
      • Strings and Conditionals
      • Using Developer Tools
      • Functions
      • Problem solving
      • Project: Rock paper scissors
      • Writing clean code
      • Arrays and Loops
      • The DOM
      • Project: Etch-A-Sketch
      • Objects and More Arrays
      • Project: Calculator
    • Backend
      • Frameworks
    • Next steps
  • Deep dives
    • Computer Science
      • Pseudocode and algorithms
      • Recursion and algorithms
        • Project: Fibs and sorting
        • More on algorithms
        • Big O
        • Project: Practicing Big O
      • Data structures
        • Maps, Stacks and Queues
        • Project: Stacks and Queues
        • Nodes, Linked Lists and Trees
        • Project: Linked Lists
        • Project: Trees
        • Next steps
    • Databases
      • Databases and SQL
      • Project: SQL Zoo
    • Design / UX
      • Fonts and typography
      • Grids
      • Project: Teardown
      • Responsive design
      • Project: Mobile friendly
      • CSS frameworks
      • Project: Bootstrapping
    • HTML / CSS
      • HTML Basics
        • Linking
        • Images and media
        • Project: Embedding media
        • HTML5
        • Tables
        • Lists
        • Forms
        • Project: Make a form
      • CSS Basics
        • Box model
        • Floats and positioning
        • Flexbox
        • Grids
        • Project: Breaking news
        • Best practices
        • Backgrounds and gradients
        • Project: One more thing
        • CSS3
        • Preprocessors
        • Project: Your own framework
      • Next steps
    • JavaScript
      • Refresher
      • Organization
      • Objects and constructors
      • Project: Library
      • Factory functions and module patterns
      • Project: Tic Tac Toe
      • Classes
      • ES6 Modules
      • Project: Restaurant
      • Object Oriented Programming
      • Project: Todo list
      • Linting
      • Menus and sliders
      • Forms
      • ES6 features
      • JSON
      • Callbacks and promises
      • Using APIs
      • Async and Await
      • Project: Weather
      • Testing
      • Project: Testing 1-2-3
      • Advanced Testing
      • Project: Battleship
      • Backends
      • Project: Where's Waldo?
      • Project: All-Star
      • Next steps
    • NodeJS
      • Project: Going to school
      • Project: Passing the test
      • Express
        • Templates and middleware
        • CRUD and MVC
        • Project: Message board
        • Routes
        • Displaying data
        • Forms and deployment
        • Project: Inventory
      • Authentication
      • Security
      • Project: Clubhouse
      • APIs
      • Securing an API
      • Project: Blog
      • Testing
      • Testing with a database
      • Project: Social network
    • React
      • Props and State
      • Render lists and handle inputs
      • Project: CV
      • Lifecycle methods
      • Hooks
      • Project: Memory card
      • Router
      • Project: Shopping cart
      • Advanced concepts
    • Ruby
      • Installation
      • Data types
      • Variables
      • Input and Output
      • Conditionals
      • Loops
      • Arrays
      • Hashes
      • Methods
      • Enumerables
      • More enumerables
      • Nested collections
      • Blocks
      • Pattern matching
      • Debugging
      • Project: Caesar cipher
      • Project: Substrings
      • Project: Stock picker
      • Project: Bubble sort
      • Object oriented programming
      • Project: Tic Tac Toe
      • Project: Mastermind
      • Serialization
      • Project: Event manager
      • Project: Hangman
      • Computer Science
        • Recursion
        • Project: Merge Sort
        • Data structures and algorithms
        • Project: Linked Lists
        • Project: Binary Search Trees
        • Project: Knight Travails
      • Testing
      • RSpec
      • Project: Four in a row
      • Git
      • Project: Open Source
      • Project: Chess
      • Next steps
    • Ruby on Rails
      • Using Heroku
      • Installing Rails
      • Basics
        • Routing
        • Controllers
        • Views
        • Asset pipeline
        • Deployment
        • Project: Blog
      • Active Record
        • Project: Upvote
      • Forms
        • Cookies, sessions, and authentication
        • Project: Password
      • Advanced forms and Active Record
        • Associations
        • Project: Private Events
        • Callbacks
        • Menus, helpers and nested forms
        • Project: Ticket agent
      • APIs
        • External APIs
        • Project: Animals
        • Project: Photo widget
      • Mailers
        • Project: Confirmation
      • Advanced topics
        • Action Cable
      • Project: Social network
      • Next steps
  • Getting hired
    • Preparing to find a job
      • Plan a strategy
      • What companies want
      • Get yourself together
      • How to prepare
      • Project: Make your website
    • Applying and interviewing
      • Qualifying leads
      • Project: Make your resume
      • Applying for jobs
      • Preparing for an interview
      • Handling an offer
      • Final words
  • Maintained by
    • wbnns
  • License
    • CC BY-NC-SA 4.0 © 2022
Powered by GitBook
On this page
  • Introduction
  • Starting small: Fibonacci
  • Assignment 1
  • Project - Merge Sort
  • Background viewing
  • Assignment 2
  • Additional resources
  1. Deep dives
  2. Computer Science
  3. Recursion and algorithms

Project: Fibs and sorting

This project will help you understand that everything that can be done with recursion can be done with iteration; although the iteration solution may be more difficult to figure out.

PreviousRecursion and algorithmsNextMore on algorithms

Last updated 4 years ago

Introduction

This project assumes you already have experience with loops, and that you've been doing some practice with your programming outside of this Computer Science course. This project will putting your ability to use recursion through a basic test, and allowing you to compare what you do with recursion with what you do with iteration (loops). This project will also help you understand that everything that can be done with recursion can be done with iteration; although the iteration solution may be more difficult to figure out.

Starting small: Fibonacci

This is an age-old classic example of something that can be solved recursively. The is a sequence where each number, or term, is the sum of the two terms before it; with the first two terms being 0 and 1. So your sequence is the following:

0, 1, 1, 2, 3, ...

Assignment 1

In your language of choice...

  1. Write a method #fibs which takes a number and returns that many members of the fibonacci sequence. Use iteration for this solution.

  2. Now write another method #fibs_rec which solves the same problem recursively.

  3. Run both these programs to find the first 5 terms. The result should look something like the example above!

  4. Make a mental note of how long both these programs to solve your problem for 5 terms.

  5. Now run both of these programs to find the first 30 terms.

  6. Is there any noticeable differences in performance between the two programs? Can you figure out why?

Project - Merge Sort

This is a classic algorithm question; and one that lends itself very well to recursion, the topic at hand! It is an algorithm which, as the name suggests, tackles the problem of sorting data sets. This method of sorting arrays may be alien to you at first; but the main thing to keep in mind that this is a Divide and Conquer algorithm. Here is some background viewing to understand what merge sort is:

Background viewing

The first step is to actually understand what the merge sort algorithm is doing:

Assignment 2

  1. Build a method #merge_sort that takes in an array and returns a sorted array, using a recursive merge sort methodology.

  2. Tips:

    1. Think about what the base case is and what behavior is happening again and again and can actually be delegated to someone else (e.g. that same method!).

    2. It may be helpful to check out the background videos again if you don't quite understand what should be going on.

  3. (OPTIONAL) Build a second method #merge_sort_iter that achieves merging behaviour, but iteratively rather than recursively.

Additional resources

This section contains helpful links to other content. It isn't required, so consider it supplemental for if you need to dive deeper into something.

Check out from Harvard's CS50x course.

Check out by David J. Malan (watch only until 1:14:00).

and on YouTube give you a more formal look at this problem if you're still unclear.

Another look at

For more attempts at recursion try the first 5 problems in

Fibonacci Sequence
this introductory video
this more detailed explanation
Merge Sort -- How it Works part 1
Merge Sort -- How it Works part II
merge sort
Project Euler