In this lesson, we will dive into functional programming and recursion. A recursive procedure solves a large problem by making it a little bit smaller somehow and then calling itself. When it calls itself, it makes the problem smaller yet again. This continues until the problem is small enough to be trivially solved.
Recursion can be hard to get used to if you have never used it before. Some things to remember when programming recursively are:
For this lesson, you should understand the very basics of Racket and know proper syntax.
In this lesson, you will learn recursion.
Here are the relevant readings for this lesson:
If you'd like more resources, check out all of the readings for Unit 0.
Before we talk about functions in computer science, let's talk about functions in math. In math, a function [mathjaxinline]f(x)[/mathjaxinline] takes a single input [mathjaxinline]x[/mathjaxinline], does "something" to that [mathjaxinline]x[/mathjaxinline], and returns a new value. For each [mathjaxinline]x[/mathjaxinline] that the function takes in, it returns only one value, and it returns the same value every time. For example, if [mathjaxinline]f(x) = x + 2[/mathjaxinline], every single time we plug in 4 to [mathjaxinline]f(x)[/mathjaxinline], we will get 6. In no circumstance will we input 4 and get 5, 7, or anything other than 6.
It's the same thing in computer science! A function is defined as a procedure that has the property that the output is dependent on the inputs--that is, when given a certain input(s) to a function, it returns the same output every time.
(define (square x) (* x x))
is a function because whenever we put in an input, we always get that input times itself.
In addition to functions, Racket also has a more general type of data type
called a procedure. A procedure is like a function, but it does not have to
necessarily return the same output for every input. For example,
square is a
random is not, because for the same input, we can get a
different output for each call of random.
To clarify: in Racket, all functions are procedures, but not all procedures are functions.
Here are some things covered in this subsection:
Functions--what they are, how to define them.
Start the next subsection 1!