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
  • Learning outcomes
  • Assignment
  • Additional resources
  1. Deep dives
  2. Ruby
  3. Computer Science

Recursion

Learn more about when and how to use recursion.

PreviousComputer ScienceNextProject: Merge Sort

Last updated 4 years ago

Introduction

Recursion is the idea that a function calls itself. Pretty simple, right? It's used to take a big problem and start breaking it down into smaller and smaller pieces ("Divide and Conquer") and continuing to feed their solutions back into the original function until some sort of answer is achieved and the whole chain unwinds.

From the :

In computer science, divide and conquer (D&C) is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

There's also a right and wrong way to use recursion. The fact is, any problem you can solve recursively you can also solve using the iterators that you know and love. If you find yourself saying "why didn't I just use a while loop here?" then you probably should have. You won't often end up using a recursive solution to a problem, but you should get a feel for when it might be a good idea. Some problems also break down into far too many pieces and totally overwhelm your computer's memory. There's a balance.

In this brief lesson, you'll get a chance to learn more about when and how to use recursion and then in the next project you will get the chance to apply some of that (since it probably won't really stick until you've had a chance to try it).

Learning outcomes

Look through these now and then use them to test yourself after doing the assignment

  • Why is recursion a useful technique for solving a big problem?

  • What are the limitations of using recursive solutions?

  • What types of problems are more suited for simple loops than recursion?

  • What is meant by "recursive depth?"

  • What is a "stack overflow" (the concept, not the website)?

  • Why is that relevant to a recursive problem?

Assignment

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.

Read the in the Bastards Book of Ruby by Dan Nguyen.

Watch this from CS50.

Read the to get an overview of some of the limitations of recursion.

Complete the on Recursion.

on Stack Overflow

, which covers recursion at the top

from Khan Academy

Wikipedia entry on Divide and Conquer Algorithms
Chapter on Recursion
Video on Recursion
"Implementation Issues" section of the wiki article
Code Quiz
"What is Ruby Recursion and How Does It Work?"
Efficient Recursion from U of Alberta
Natashatherobot's blog post on Recursion in Ruby
Functional Programming Techniques with Ruby post
A breakdown of the recursive Fibonacci method