Learn Programming: Subroutines (Functions and Procedures)

Image credits: Image created by the author using the program Spectacle.

Requirements

In the introduction to development environments, I have mentioned Python, Lua and JavaScript as good choices of programming languages for beginners. Later, I have commented about GDScript as an option for people who want to program digital games or simulations. For the introductory programming activities, you will need, at least, a development environment configured for one of the previous languages.

If you wish to try programming without configuring an environment, you can use of the online editors that I have created:

However, they do not provide all features offered by interpreters for the languages. Thus, sooner or later, you will need to set up a development environment. If you need to configure one, you can refer to the following resources.

Thus, if you have an Integrated Development Environment (IDE), or a combination of text editor and an interpreter, you are ready to start. The following example assumes that you know how to run code in your chosen language, as presented in the configuration pages.

If you want to use another language, the introduction provides links for configure development environments for the C, C++, Java, LISP, Prolog, and SQL (with SQLite) languages. In many languages, it suffices to follow the models from the experimentation section to modify syntax, commands and functions from the code blocks. C and C++ are exceptions, for they require pointers access the memory.

Subroutines, Modularization, and Code Reuse

In conditional structures, the convenience of thinking in the source code of a program as a composition of blocks was commented. Starting from this topic, you will begin creating your own reusable source code blocks as subroutines.

Virtually every programming language (in a way of another) provides resources to create functions, procedures, and/or methods. Although the terms are slightly different and have their own particularities, the term subroutine can serve as a generic word for any of them.

A subroutine (or subprogram) is a block of code that, when called, runs a sequence of instructions defined by a programmer. Subroutines are useful because they allow defining a single time a code block that performs a same processing or operation, though it can be used whenever necessary.

Functional decomposition is a good programming practice. A program that is decomposed by subroutines is said modular, because the practice is called modularization. As subroutines can be used multiple time after the definition, modularization promotes code reuse. With good choices for names, subroutines can also make it easier to read and understand the source code, reducing the need for comments.

Functions

Function are, perhaps, the most traditional type of subroutines, because they are alike Mathematics functions. Nevertheless, functions in programming are more flexible and potentially more powerful than Math ones.

In Mathematics, a function is a relation that calculates a result from parameters. Functions have a domain, that specify a set of acceptable values, and an imagine, that specify possible results. For instance, the modulus (not related to modularization nor to division remainder) or absolute value of a number maps real to numbers to their respective non-negative values.

The function can be used as many times as needed, for any value that is considered valid (in this case, real numbers).

In programming, a function is a block of code that performs a processing and returns a result. A function may (or may not) have parameters. When they exist, each parameter will have an expected type to specify the potentially valid values. The implementation can impose additional limits to accepted or restricted values, determining the valid values.

Thus, in general, a function has a structure the resembles the following pseudocode.

function name_of_function(parameter1: type1, parameter2: type2, ...) type of return
begin
    // Local variables
    return type result
    // ...
    // Implementation
    // ...
    return result
end

The exact syntax tend to vary among programming languages. For instance, a possible implementation for the module function in JavaScript can correspond to the following code. To explore it, you can use the embedded console of your browser (shortcut: F12). If you would rather test the implementation in Python, Lua or GDScript, the code is also available in the respective tab.

function f(x) {
    let y
    if (x >= 0) {
        y = x
    } else {
        y = -x
    }
    return y
}

def f(x):
    if (x >= 0):
        y = x
    else:
        y = -x
    return y

function f(x)
    local y
    if (x >= 0) then
        y = x
    else
        y = -x
    end
    return y
end

func f(x):
    var y
    if (x >= 0):
        y = x
    else:
        y = -x
    return y

Once one defines the f() function, she/he can use it whenever she/he wants to retrieve the corresponding non-negative value passed as a parameter for the function. In other words, instead of repeating the code, it suffices to use the created function. The use of a function is named function call.

For the next examples, the code for the function definition must appear before the call. It must exist only once in a program.

// ...

console.log(f(1))
console.log(f(0))
console.log(f(-1))

# ...

print(f(1))
print(f(0))
print(f(-1))

-- ...

print(f(1))
print(f(0))
print(f(-1))

extends Node

# ...

func _ready():
    # ...

    print(f(1))
    print(f(0))
    print(f(-1))

When a function call is performed, the program performs a jump the code of the function's definition, performs the defined processing, gathers the result for, next, jump back to the code that called the function to provide the calculated result. In programming languages, all the previous steps are performed by the interpreter or compiler. For a programmer, it suffices to call the function by its name.

Thus, instead of generic names, it is convenient to adopt self-describing names for subroutines. Although the name is indifferent for the compiler or interpreter (although it must be unique), clean and descriptive names are more appropriate to people that program the system.

For instance, instead of f(), a function that calculates the absolute value of a number could be called absolute_value(). Likewise, instead of x, the parameter could be called number or value. The calculated result could be named result.

// Definition.
function absolute_value(value) {
    let result
    if (value >= 0) {
        result = value
    } else {
        result = -value
    }
    return result
}

// Usage.
console.log(absolute_value(1))
console.log(absolute_value(0))
console.log(absolute_value(-1))

# Definition.
def absolute_value(value):
    if (value >= 0):
        result = value
    else:
        result = -value
    return result

# Usage.
print(absolute_value(1))
print(absolute_value(0))
print(absolute_value(-1))

-- Definition.
function absolute_value(value)
    local result
    if (value >= 0) then
        result = value
    else
        result = -value
    end
    return result
end

-- Usage.
print(absolute_value(1))
print(absolute_value(0))
print(absolute_value(-1))

# Definition.
extends Node

func absolute_value(value):
    var result
    if (value >= 0):
        result = value
    else:
        result = -value
    return result

func _ready():
    # Usage.
    print(absolute_value(1))
    print(absolute_value(0))
    print(absolute_value(-1))

The result is a code that is simpler to read and understand.

Besides syntax differences, there are programming languages (such as C, C++, JavaScript and GDScript) that define that a function must return a single value. Other programming languages (such as Lua and Python) allow a function to return multiple values at once (for instance, return x, y).

In practice, languages that limit one value per return can use composite data types to return many values in a single variable. Thus, the limitation will become milder after the introduction of data structures and records.

Procedures

In Mathematics, functions are created to calculate results. The goal is obtaining the calculated result.

In programming, there are times that the goal to define a subroutine is a side effect instead of a result. Side effects can include, for instance, change of state (variable values) of a program, writing data, reading data, wait for a time interval.

To distinguish subroutines that return values from subroutines in which the goal is the resulting side effect, one can use the term function for the first category and procedure for the second. However, the distinction is often more theoretical than practice; the terminology can change among authors. In fact, there are programming languages that use the term function for any subroutine (or empty function, or void function for procedures). Likewise, there are programming languages that use the term procedure for any subroutine.

To make the goal of each subroutine explicit, this material adopt the terms function and procedure.

This, in general, a procedure will have the following form:

procedure name_of_procedure(parameter1: type1, parameter2: type2, ...)
begin
    // Local variables
    // ...
    // Implementation
    // ...
end

It can be noted that are not information about the type of return, nor a return value.

For an example, one you define a procedure to write result of the absolute value of a number using the previously defined absolute_value() function. Although you could write any name for your subroutine, it is common to use verbs in the imperative mood for names. Thus, the procedure could be called something like write_absolute_value(). Another option could be print_absolute_value().

// Definition.
function write_absolute_value(value) {
    // The function absolute_value() must be defined.
    let result = absolute_value(value)
    console.log("|", value, "| = ", result)
}

// Usage.
write_absolute_value(1)
write_absolute_value(0)
write_absolute_value(-1)

# Definition.
def write_absolute_value(value):
    # The function absolute_value() must be defined.
    result = absolute_value(value)
    print("|", value, "| = ", result)

# Usage.
write_absolute_value(1)
write_absolute_value(0)
write_absolute_value(-1)

-- Definition.
function write_absolute_value(value)
    -- The function absolute_value() must be defined.
    local result = absolute_value(value)
    print("|", value, "| = ", result)
end

-- Usage.
write_absolute_value(1)
write_absolute_value(0)
write_absolute_value(-1)

extends Node

# Definition.
func write_absolute_value(value):
    # The function absolute_value() must be defined.
    var result = absolute_value(value)
    print("|", value, "| = ", result)

func _ready():
    # Usage.
    write_absolute_value(1)
    write_absolute_value(0)
    write_absolute_value(-1)

Thus, subroutines use other previously defined subroutines, making the code even more modular. Reusable subroutines can also be grouped in an own file to define a library. When you use a command use as include or import in a programming language, you are loading, among other, definitions of subroutines to use in your programs.

Hereafter, you can start creating your own libraries if you group the subroutines that you write in a file. For instance, your library can be called your_name.js, your_name.lua, your_name.py and/or your_name.gd. When you wish to use them, it suffices to import the file to load the source code and definition. Depending on programming language and the interpreter (or compiler), it may be necessary to modify the command to generate the project. If you are using an IDE, it is probably that is can do can perform this task automatically for you (provided that the creation of the file was performed using the tool).

Methods

In object-oriented programming languages (Object-Oriented Paradigm or OOP), functions or procedures belonging to a class are called methods. A practical difference that distinguishes methods from the other types of subroutines is the possibility to modify the internal state of objects of a class, stored in variables (called attributes).

At this time, as the goal is not learning OOP, it is not necessary to worry with the terminology. It suffices to know that, when a call such as variable.call(parameter) is performed instead of call(variable, parameter), the first case uses a method, while the second one uses a function or procedures.

Therefore, now you understand why there are subroutines in programming languages that use a value or a variable before the call: it is because you are using a method call.

Terminology and Techniques

Subroutines are important for programming. There even exists programming paradigms (such as Functional Programming) that focus on building programs as compositions of functions.

Given their importance, it is worth to know more about the related terminology and techniques to define and use functions, procedures and methods.

Declaration, Signature, Documentation, Prototype and Forward Declaration

The signature of a subroutine is the combination of name, return type and parameters (names and types). When one reads the signature, she/he can identify what must be provided to a function.

For simple functions (or procedures) or with good parameter names, it is possible to identify parameters by name. For complex functions (or procedures) or with names that are not sufficiently good to understand the purpose, it is usual to document:

A description of what the subroutine does;
A description of the expected parameters (including valid and invalid values);
The returned value, if it exists.

There are some special formatting to document subroutines, adopted by tools that generate documentation using markups. Some popular options include:

The supported programming languages vary from tool to tool. An advantage of the tools is the possibility of generating HTML pages with documentation. For instance, the Application Programming Interface (API) documentation for KDE is created using Doxygen (alongside KApiDox, created by KDE).

Some programming languages also allowing defining doc strings, that are strings provided in a subroutine's definition to document it.

Python provides doc strings and is supported by Doxygen. The following example illustrates the creation of a doc string in Doxygen format. For more information, one can consult the Doxygen's documentation for Python.

def absolute_value(value):
    """! Mathematical function to calculate the absolute value (module) of a number.

    @param value  An integer or real number to be used in the calculus.

    @return  The absolute value of value.
    """

    if (value >= 0):
        result = value
    else:
        result = -value

    return result

There other markup (for instance, to example of use). Good documentation informs about the expected use for the subroutine, eliminating the need to read the source code to know what it does.

def absolute_value(value):
    """! Mathematical function to calculate the absolute value (module) of a number.

    @param value  An integer or real number to be used in the calculus.

    @return  The absolute value of value.
    """

Reading the previous documentation, one can infer that a valid use for absolute_value() could resemble abolute_value(-1.234) to calculate .

The declaration of a subroutine is, usually, the combination of the signature with the implementation. Programming languages commonly allow the use of functions that were defined before the call. In some programming languages (such as C and C++), there also exists the concepts of prototype and forward declaration, which allows to notify the compiler about the existence of a function (using its signature) before its implementation. Prototypes and forward declaration provide a feature to work around the issue of definition before call.

Arguments and Parameters

Technically, there are two terms for values passed and received by subroutines. An argument is the value passed in a subroutine call. A parameter is the value received by the subroutine after the call.

In practice, both terms are often used indistinctly.

Passing Parameters

Some programming languages allow passing parameters to subroutines in different ways. The two most commons ways of passing parameters are passing by value and passing by reference, though there exist others. For instance, a third common type is called passing by assignment (used, for instance, in Python).

When passing by value, the value received by the subroutine is a copy of the original. In other words, the subroutine can modify the received value without modifying the original one. One can think of the parameter as an additional local variable of the subroutine.

When passing by reference, the received value is a memory address or a reference to the variable that stores the original value. Thus, if the subroutine modifies the received value, the value is also modified in the code that called the subroutine. In other words, every value modification will be permanent and will affect the rest of the program.

When passing by assignment, the behavior of the parameter varies according to what the assignment operator would do with the variable. For instance, if the alteration was performed by reference (using a memory address), the value modification will affect the original variable. Otherwise, the variable will be considered a copy.

Programming languages can also vary the passage behavior according the data type. In many programming languages, it is common that the passage of primitive types are passed by value or equivalent. Composite data type and data structures, on the other hand, are commonly passed by reference or equivalent.

At this time, all types passed to subroutines will be of primitive types. Thus, it can be assumed, for now, that every passage will be performed by value, except case commented otherwise.

Polymorphism

In programming, Polymorphism allows, among others, defining versions of a subroutine with a very same name, but with different types (or quantities) of parameters. This type of polymorphism is called ad-hoc (coercion is another example of ad-hoc polymorphism).

For instance, instead of a defining a subroutine for real numbers (add_real(x: real, y: real): real) and one for integer numbers (add_integers(x: integer, y: integer): inteiro), it would be possible to define both with the same name, but with different types. In other words, add(x: integer, y: integer): integer and add(x: real, y: real): real.

This is practical because it allows creating a common programming interface for different data types. In programming languages that do not support this kind of polymorphism, it can be necessary to prefix or suffix the name of the subroutine.

First-Class Functions (or Functions as First-Class Citizens) and Anonymous (Lambda) Functions

Some programming languages (such as Lua, JavaScript and Python) allow storing function references in variables, pass them as parameters for other subroutines or return them from other subroutines. In such cases, it is said the language considers functions (or subroutines, in general), as first-class citizens.

The passage of subroutines as parameters for other subroutines or the return of a subroutine from another subroutine are also called high-order functions. It does not mean passing a result of a subroutine call, though the own code of the subroutine.

Some programming languages also provide a resource called anonymous function, more known as lambda (Greek letter ou ).

let write_lowercase = function(text) {
    console.log(text.toLowerCase())
}

function write_uppercase(text) {
    console.log(text.toUpperCase())
}

function write_hello_franco(write_function) {
    write_function("Hello, Franco!")
}

write_hello_franco(write_lowercase)
write_hello_franco(write_uppercase)

write_lowercase = lambda text: print(text.lower())

def write_uppercase(text):
    print(text.upper())

def write_hello_franco(write_function):
    write_function("Hello, Franco!")

write_hello_franco(write_lowercase)
write_hello_franco(write_uppercase)

-- The omission of local defines write_lowercase as a global function.
write_lowercase = function(text)
    print(text:lower())
end

function write_uppercase(text)
    print(text:upper())
end

function write_hello_franco(write_function)
    write_function("Hello, Franco!")
end

write_hello_franco(write_lowercase)
write_hello_franco(write_uppercase)

# Warning:
# This block of code **will not work** in current versions (2021) of the engine.
# The version 3 of Godot does not support anonymous (lambda) functions.
# The version 4 plants to support lambda functions.
# Thus, the following example requires the version 4 (under development) for use.
# Consult:
# - <https://godotengine.org/article/gdscript-progress-report-feature-complete-40>
# - <https://github.com/godotengine/godot-proposals/issues/2431>
# - <https://github.com/godotengine/godot/pull/38645>

extends Node

var write_lowercase = func(text):
    print(text.to_lower())

func write_uppercase(text):
    print(text.to_upper())

func write_hello_franco(write_function):
    write_function.call("Hello, Franco!")

func _ready():
    write_hello_franco(write_lowercase)
    write_hello_franco(write_uppercase)

The previous example illustrates:

The definition of a function stored in a variable;
The passage of a function as a parameter to another function;
A call of the function stored in a variable.

In this case, all functions are procedures, though the principle is the same.

Although this can be a more advanced resource, it is interesting to know it. Besides being common in programming languages from the functional paradigm, some modern frameworks, such as React, use first-class functions as a programming technique. For instance, they can be used as replacements for conditional and repetition structures to filter data (that is, to select elements with certain values).

Tests

The use of subroutines can make it easier to test and debug program in various ways.

The definition of subroutines centers the implementation of a feature in a single place. This makes it easier to modify the source code, and restricts possible regions for errors. For instance, if a function has return an incorrect value, one can infer that there exists a problem in that function's definition, in another subroutine used by the function, or in the provided parameter.

Furthermore, there are techniques for testing that can be used for functions. One of the most popular is called unit test. The unit test threats the implementation of a function as black box. For each test case in a unit test, one defines combinations of parameters with expected results for the call using the defined values. If the obtained result differs from the expected one, one knows that there exists implementation problems.

For instance, for absolute_value(), one could define the following test cases:

: input , expected output: ;
: input , expected output: ;
: input , expected output: ;
: input , expected output .
: input , expected output .

console.log(absolute_value(-1))
console.log(absolute_value(-1.23))
console.log(absolute_value(0))
console.log(absolute_value(1))
console.log(absolute_value(1.23))

print(absolute_value(-1))
print(absolute_value(-1.23))
print(absolute_value(0))
print(absolute_value(1))
print(absolute_value(1.23))

print(absolute_value(-1))
print(absolute_value(-1.23))
print(absolute_value(0))
print(absolute_value(1))
print(absolute_value(1.23))

print(absolute_value(-1))
print(absolute_value(-1.23))
print(absolute_value(0))
print(absolute_value(1))
print(absolute_value(1.23))

It can be noted that there exists cases in which it is possible to define test cases even before implementing a subroutine. In fact, there exists a software development process called test-driven development (TDD), which recommends creating tests before implementing a program (or of each new feature).

Combining function calls with relational operators, it is possible to start automating a test process. For instance, in the next cases, any False or false print would show a failure in a test case.

console.log(absolute_value(-1) === 1)
console.log(absolute_value(-1.23) === 1.23)
console.log(absolute_value(0) === 0)
console.log(absolute_value(1) === 1)
console.log(absolute_value(1.23) === 1.23)

print(absolute_value(-1) == 1)
print(absolute_value(-1.23) == 1.23)
print(absolute_value(0) == 0)
print(absolute_value(1) == 1)
print(absolute_value(1.23) == 1.23)

print(absolute_value(-1) == 1)
print(absolute_value(-1.23) == 1.23)
print(absolute_value(0) == 0)
print(absolute_value(1) == 1)
print(absolute_value(1.23) == 1.23)

print(absolute_value(-1) == 1)
print(absolute_value(-1.23) == 1.23)
print(absolute_value(0) == 0)
print(absolute_value(1) == 1)
print(absolute_value(1.23) == 1.23)

To continue improving the solution, it is possible to create a test subroutine. The example below defined a procedure called unit_test() that compares if an obtained result is equal to the expected result for the test. If the results are different, the procedure writes a message informing about the failure in the test case. To illustrate the use, the implementation of absolute_value() was modified to always provide an incorrect value for negative numbers.

function unit_test(name, obtained_result, expected_result) {
    if (obtained_result !== expected_result) {
        console.log(name, " has failed. Expected result: ", expected_result, ". Obtained result: ", obtained_result)
    }
}

function absolute_value(value) {
    let result
    if (value >= 0) {
        result = value
    } else {
        result = -12345 // Wrong!
    }
    return result
}

unit_test("|-1|", absolute_value(-1), 1)
unit_test("|-1.23|", absolute_value(-1.23), 1.23)
unit_test("|0|", absolute_value(0), 0)
unit_test("|1|", absolute_value(1), 1)
unit_test("|1.23|", absolute_value(1.23), 1.23)

def unit_test(name, obtained_result, expected_result):
    if (obtained_result != expected_result):
        print(name, " has failed. Expected result: ", expected_result, ". Obtained result: ", obtained_result)

def absolute_value(value):
    if (value >= 0):
        result = value
    else:
        result = -12345 # Wrong!
    return result

unit_test("|-1|", absolute_value(-1), 1)
unit_test("|-1.23|", absolute_value(-1.23), 1.23)
unit_test("|0|", absolute_value(0), 0)
unit_test("|1|", absolute_value(1), 1)
unit_test("|1.23|", absolute_value(1.23), 1.23)

function unit_test(name, obtained_result, expected_result)
    if (obtained_result ~= expected_result) then
        print(name, " has failed. Expected result: ", expected_result, ". Obtained result: ", obtained_result)
    end
end

function absolute_value(value)
    local result
    if (value >= 0) then
        result = value
    else
        result = -12345 -- Wrong!
    end
    return result
end

unit_test("|-1|", absolute_value(-1), 1)
unit_test("|-1.23|", absolute_value(-1.23), 1.23)
unit_test("|0|", absolute_value(0), 0)
unit_test("|1|", absolute_value(1), 1)
unit_test("|1.23|", absolute_value(1.23), 1.23)

extends Node

func unit_test(name, obtained_result, expected_result):
    if (obtained_result != expected_result):
        print(name, " has failed. Expected result: ", expected_result, ". Obtained result: ", obtained_result)

func absolute_value(value):
    var result
    if (value >= 0):
        result = value
    else:
        result = -12345 # Wrong!
    return result

func _ready():
    unit_test("|-1|", absolute_value(-1), 1)
    unit_test("|-1.23|", absolute_value(-1.23), 1.23)
    unit_test("|0|", absolute_value(0), 0)
    unit_test("|1|", absolute_value(1), 1)
    unit_test("|1.23|", absolute_value(1.23), 1.23)

The unit_test() procedure is limited, serving only to illustrate the practice. For instance, a limitation of the implementation is that is expects that the results are equal. There exists cases in which it could be preferable to use other logic and/or relational operators for the automatic checking.

Many programming languages have frameworks to make it easier to create test cases and verify them automatically. For instance, Python has the unittest module (documentation) for the definition of unit tests. Many IDEs also provide integration with test frameworks, making it even easier to test a project.

Refactoring

Besides tests, subroutines are commonly used to refactor systems. A refactoring modifies the original code to transform it into an equivalent code that is simpler, more efficient, easy to understand, and/or to maintain (maintainability).

A common refactoring technique used with subroutine is called function (or procedure or method) extraction. For an example, you can consider the following code.

let x = -1
if (x < 0) {
    x = -x
}

let y = 2
if (y < 0) {
    y = -y
}

let z = -3
if (z < 0) {
    z = -z
}

console.log(x)
console.log(y)
console.log(z)

x = -1
if (x < 0):
    x = -x

y = 2
if (y < 0):
    y = -y

z = -3
if (z < 0):
    z = -z

print(x)
print(y)
print(z)

local x = -1
if (x < 0) then
    x = -x
end

local y = 2
if (y < 0) then
    y = -y
end

local z = -3
if (z < 0) then
    z = -z
end

print(x)
print(y)
print(z)

extends Node

func _ready():
    var x = -1
    if (x < 0):
        x = -x

    var y = 2
    if (y < 0):
        y = -y

    var z = -3
    if (z < 0):
        z = -z

    print(x)
    print(y)
    print(z)

The block performs a same operation three times, with different variables. One can observe that an implementation as the one used for absolute_value() would generate equivalent code.

function absolute_value(value) {
    let result
    if (value >= 0) {
        result = value
    } else {
        result = -value
    }
    return result
}

let x = absolute_value(-1)
let y = absolute_value(2)
let z = absolute_value(-3)

console.log(x)
console.log(y)
console.log(z)

def absolute_value(value):
    if (value >= 0):
        result = value
    else:
        result = -value
    return result

x = absolute_value(-1)
y = absolute_value(2)
z = absolute_value(-3)

print(x)
print(y)
print(z)

function absolute_value(value)
    local result
    if (value >= 0) then
        result = value
    else
        result = -value
    end
    return result
end

local x = absolute_value(-1)
local y = absolute_value(2)
local z = absolute_value(-3)

print(x)
print(y)
print(z)

extends Node

func absolute_value(value):
    var result
    if (value >= 0):
        result = value
    else:
        result = -value
    return result

func _ready():
    var x = absolute_value(-1)
    var y = absolute_value(2)
    var z = absolute_value(-3)

    print(x)
    print(y)
    print(z)

Thus, the code has been refactored using a function.

In general, except if the implementation is trivial, it is convenient to extract common code to subroutines to avoid duplicating source code. Some IDEs provide resources for function, procedure and method extraction. When available, one can select a region of source code with the desired code and search for an option such as Refactor: Extract method (or equivalent).

Recursion

Subroutines can call other subroutines. In particular, a call that a subroutine makes to the very same subroutine has a special name: recursion.

Recursion is not an exclusive characteristic of programming. It is common in Mathematics, and it can also be found in the nature. For instance, there are plants such as trees that look like recursive structures. Another example are fractals.

A recursive subroutine has two parts:

One base case (or more), also called stop condition, that defines an immediate result to end the recursion;
A recursive step, recursive formula or recurrence equation, that simplifies the problem progressively as a function of itself, until reaching the basis case.

A common joke to explain recursion is creating a link that lead to itself, such as this one. The joke works because the browser will follow the link once, serving as recursive call and the base case to stop.

One the most famous examples of recursive equations are factorial numbers. A factorial number is a number generated by the expression , with (read as zero factorial) defined as and a natural number. For instance, .

The factorial has the following definition:

As programs can have more than an exit point, a subroutine can have more than one possibility to return (albeit each call returns a single time). This make it possible to write recursive code.

function factorial(x) {
    if (x === 0) {
        return 1
    }
    else {
        return x * factorial(x - 1)
    }
}

def factorial(x):
    if (x == 0):
        return 1
    else:
        return x * factorial(x - 1)

function factorial(x)
    if (x == 0) then
        return 1
    else
        return x * factorial(x - 1)
    end
end

extends Node

func factorial(x):
    if (x == 0):
        return 1
    else:
        return x * factorial(x - 1)

The previous code is equivalent to the following, because the use of return ends the current function call once run.

function factorial(x) {
    if (x === 0) {
        return 1
    }

    return x * factorial(x - 1)
}

def factorial(x):
    if (x == 0):
        return 1

    return x * factorial(x - 1)

function factorial(x)
    if (x == 0) then
        return 1
    end

    return x * factorial(x - 1)
end

extends Node

func factorial(x):
    if (x == 0):
        return 1

    return x * factorial(x - 1)

The use of recursion allows defining code that repeat itself, proving an alternative to the use of repetition structures (loops). It must be noted that there exists a maximum limit for recursive calls; if it is exceeded, an error called stack overflow occurs.

For beginners, a stack overflow often suggests an incorrect implementation of a recursive algorithm. For instance, in JavaScript:

function incorrect_factorial(x) {
    if (x === 0) {
        return 1
    }

    return x * incorrect_factorial(x) // Wrong!}

A call to the previous code (for instance, incorrect_factorial(5)) would never end, because the recursive call does not simplify the problem. Rather, it uses the same value received as a parameter, instead of approximating it of the base case with a subtraction. In practice, it will end with a stack overflow, for the memory of a computer is finite, imposing a maximum limit of recursive calls that it can store.

There is a particular case of recursion called tail recursion (also called tail-call optimization). It allows optimizing recursive code to, potentially, minimize the consumption of memory, improve the subroutine, and avoid a stack overflow. Potentially because it is not every programming that performs optimizations for tail recursion. For instance, Lua and JavaScript do perform tail recursion optimization, though Python does not. Although I am not sure, I believe that GDScript does not, either.

As the explanation of tail recursion would require an explanation about a data structure called stack, this topic will only provide an example.

function tail_recursion_factorial(x, result) {
    if (x === 0) {
        return result
    }

    return tail_recursion_factorial(x - 1, x * result)
}

function factorial(x) {
    return tail_recursion_factorial(x, 1)
}

def tail_recursion_factorial(x, result):
    if (x == 0):
        return result

    return tail_recursion_factorial(x - 1, x * result)

def factorial(x):
    return tail_recursion_factorial(x, 1)

function tail_recursion_factorial(x, result)
    if (x == 0) then
        return result
    end

    return tail_recursion_factorial(x - 1, x * result)
end

function factorial(x)
    return tail_recursion_factorial(x, 1)
end

extends Node

func tail_recursion_factorial(x, result):
    if (x == 0):
        return result

    return tail_recursion_factorial(x - 1, x * result)

func factorial(x):
    return tail_recursion_factorial(x, 1)

To use the example, one could make a call such as tail_recursion_factorial(5, 1), always providing the initial result 1. However, to avoid errors and making the use more convenient, a second definition (factorial) provides the correct predefined call. For instance, factorial(5). The creation of the auxiliary function is convenient in other contexts, such as manipulation of data structures.

By the way, the use of the factorial function is useful to demonstrate integer numbers' overflow, as commented in Arithmetic and Basic Mathematics. In languages in which integer numbers are composed by a fixed number of bytes, such as 32 bits (4 bytes) or 64 bits (8 bytes), an overflow will occur quickly. You can verify the occurrence making calls such as:

factorial(5);
factorial(6);
factorial(7);
factorial(8);
factorial(12);
factorial(13);
factorial(14);
factorial(17);
factorial(20);
factorial(21);
factorial(22).

Depending on the language, some obtained values for following calls will be less than the previous value. The values can even become negative. This happens due to overflow.

Assertions

The example for factorial use natural numbers, though programming languages provide integer numbers. How to avoid the calculation for negative numbers?

One option is to use an impossible result to mark an error. For instance, return -1 for the input of a negative parameter.

function factorial(x) {
    if (x < 0) {
        return -1
    } else if (x === 0) {
        return 1
    } else {
        return x * factorial(x - 1)
    }
}

let result = factorial(-5)
if (result !== -1) {
    console.log(result)
} else {
    console.log("Invalid parameter.")
}

def factorial(x):
    if (x < 0):
        return -1
    elif (x == 0):
        return 1
    else:
        return x * factorial(x - 1)

result = factorial(-5)
if (result != -1):
    print(result)
else:
    print("Invalid parameter.")

function factorial(x)
    if (x < 0) then
        return -1
    elseif (x == 0) then
        return 1
    else
        return x * factorial(x - 1)
    end
end

local result = factorial(-5)
if (result ~= -1) then
    print(result)
else
    print("Invalid parameter.")
end

extends Node

func factorial(x):
    if (x < 0):
        return -1
    elif (x == 0):
        return 1
    else:
        return x * factorial(x - 1)

func _ready():
    var result = factorial(-5)
    if (result != -1):
        print(result)
    else:
        print("Invalid parameter.")

A second possibility is using exceptions, in languages that support them.

Another possibility is to use an assertion (assert) to highlight an incorrect use of the function. An assertion defines a conditional that must be true for the correct use of a subroutine. It defines a contract: it is expected that the condition is valid for the result to be correct. If the conditional fails, the program will crash with an error message.

It should be noted that assertions must not be used for validation of programs used by end-users (for instance, for input validation), though only to show errors during development time. In many implementations, assertions are disabled for final version of programs (called release, created for distribution). In other words, the condition of the assertion at use time in release versions. Therefore, the correct way to handle errors involves the use of conditional structures or exceptions.

Provided the awareness of the limitation, assertions are useful during development. Many programming languages implement assertions as a command or a function.

JavaScript: the language does not provide a standard implementation for assert(). There eixsts console.assert() (documentation), though the subroutine does not interrupt the execution in case of error. In other words, in this case, the assertion serves only as a warning, limiting its usefulness.
Python: assert() (documentation);
Lua: assert() (documentation);
GDScript: assert() (documentation).

function factorial(x) {
    console.assert(x >= 0, "Factorial cannot be calculated for negative numbers")

    if (x === 0) {
        return 1
    } else {
        return x * factorial(x - 1)
    }
}

factorial(5) // OK
// factorial(-5) // Error; commented to avoid infinite loop / stack overflow.

def factorial(x):
    assert x >= 0, "Factorial cannot be calculated for negative numbers"

    if (x == 0):
        return 1
    else:
        return x * factorial(x - 1)

factorial(5) # OK
factorial(-5) # Error; program will crash and the error message

function factorial(x)
    assert(x >= 0, "Factorial cannot be calculated for negative numbers")

    if (x == 0) then
        return 1
    else
        return x * factorial(x - 1)
    end
end

factorial(5) -- OK
factorial(-5) -- Error; program will crash and the error message

extends Node

func factorial(x):
    assert(x >= 0, "Factorial cannot be calculated for negative numbers")

    if (x == 0):
        return 1
    else:
        return x * factorial(x - 1)

func _ready():
    factorial(5) # OK
    factorial(-5) # Error; program will crash and the error message

In Python, Lua and GDScript, the program will crash (or be interrupted) when the function is used with a negative number, displaying the defined message. In JavaScript, although the message is shown, the code will keep running until it is manually interrupted (for instance, closing the tab or window of the browser), on in case of stack overflow-- whatever happens first. To avoid forcing you to close the tab or window of your browser, or to avoid that it crashes because of stack overflow, the line using a negative number is commented.

Assertions can also be used to verify type type of the received parameter, as an additional guarantee of correct value.

Early Return versus Single Entry, Single Return

Some program languages restrict the use of return per subroutine. Others allow using multiple ones.

Subroutines that use a single return are called single entry, single return. Subroutines that use more than one return are said to have early return.

In particular, the use of early return can generate code that is simpler to read. The idea is to eliminate error conditions in the beginning of the definition of the subroutine, allowing that the remainder of the implementation focuses on the general case. This allows avoiding using multiple nested if.

To compare both approaches, one can consider the example of calculating the factorial returning -1 in the case of a negative number.

In the version with a single return, a variable to store the result must be declared (in this case, it is called result). Every possible result will be assigned to it. In the case of Python, None is used to denote an absence of value until the first real assignment, because the variable declaration in the language is performed using assignment. Another possibility would be declaring the variable directly in the first real assignment.

function factorial(x) {
    let result
    if (x < 0) {
        result = -1
    } else if (x === 0) {
        result = 1
    } else {
        result = x * factorial(x - 1)
    }

    return result
}

def factorial(x):
    result = None
    if (x < 0):
        result = -1
    elif (x == 0):
        result = 1
    else:
        result = x * factorial(x - 1)

    return result

function factorial(x)
    local result
    if (x < 0) then
        result = -1
    elseif (x == 0) then
        result = 1
    else
        result = x * factorial(x - 1)
    end

    return result
end

func factorial(x):
    var result
    if (x < 0):
        result = -1
    elif (x == 0):
        result = 1
    else:
        result = x * factorial(x - 1)

    return result

In the early return version, every case return immediately after handled. The implementation becomes more linear, with less branching. If one wishes, it is even possible to omit the else after each return.

function factorial(x) {
    if (x < 0) {
        return -1
    }

    if (x === 0) {
        return 1
    }

    let result = x * factorial(x - 1)

    return result
}

def factorial(x):
    if (x < 0):
        return -1

    if (x == 0):
        return 1

    result = x * factorial(x - 1)

    return result

function factorial(x)
    if (x < 0) then
        return -1
    end

    if (x == 0) then
        return 1
    end

    local result = x * factorial(x - 1)

    return result
end

func factorial(x):
    if (x < 0):
        return -1

    if (x == 0):
        return 1

    var result = x * factorial(x - 1)
    return result

By the way, it is possible to use early return in procedures. To do this, it suffices to use a return without value (that is, an empty return).

function write_if_franco(name) {
    if (name.toLowerCase() !== "franco") {
        return
    }

    console.log("Franco")
}

def write_if_franco(name):
    if (name.lower() != "franco"):
        return

    print("Franco")

function write_if_franco(name)
    if (name:lower() ~= "franco") then
        return
    end

    print("Franco")
end

func write_if_franco(name):
    if (name.to_lower() != "franco"):
        return

    print("Franco")

Personally, I prefer to write code using early return. In the version with early return, all exceptional cases return once identified or handled.

There are cases in which the version with a single return can be faster; however, instead of supposing, the best is to identify a bottleneck and use a profiler (tool to evaluate performance) to compare the performance, if it is truly needed.

Subroutines in Programming

The previous section provided some examples of using subroutines in programming languages. The next section present some additional examples as a summary, illustrating the use with flowcharts and visual programming languages.

Flowcharts: Flowgorithm

To create subroutines in Flowgorithm, you can use the option Program and choose Add Function.... Another option is clicking on the icon displaying the name Main and choose Add Function.... This same icon allow switching among existing subroutines and the main program.

Choose a name for the subroutine; if needed, defined parameters:

Add creates a new parameter. When you choose this option, you must name the new parameter and set a type for it;
Edit modify an existing parameter;
Remove erases a parameter.

Finally, choose a return type for the subroutine. If it is a procedure, choose None. Otherwise, choose a type and a name for the variable that will be returned (for instance, result).

To return to the main program, choose Main in the icon with the name of the newly-created subroutine. To add a function call, click in an arrow and choose Call. In the new block, type the name of the desired subroutine. If it has parameters, type the values between parentheses. For instance, writeMessage("Hello, my name is Franco!").

It is also possible to call subroutines in output and assignment blocks. To do this, it suffices to write the name of the subroutine, providing the parameters between parentheses.

Example of using subroutines in Flowgorithm, using the English interface.

In the image, each block started by a purple ellipsis represents a subroutine (also called subprogram in Flowgorithm). It starts with a name (such as Mainor writeMessage) and finished with an End (if it does have a return, defining a procedure) or in a Return, if it returns a value (defining a function).

The main program in the image is composed only by the created subroutines: writeMessage(), add(), writeSum() and writeCountdown().

The following code blocks transcribe the text in the image. The image has five flowcharts.

writeMessage:

writeMessage(String message)

Output message

End

add:

add(Integer x, Integer y)

Integer result
result = x + y

Return Integer result

writeSum:

writeSum(Integer x, Integer y)

Output x & " + " & y & " = " & add(x, y)

End

writeCountdown:

writeCountdown(Integer counter)

Output counter
If counter > 0
    False
    True
        writeCountdown(counter - 1)

End

Main:

Main

writeMessage("Hello, my name is Franco!")
writeMessage(ToString(add(1, 2)))
writeMessage(ToString(add(-1, -2)))
writeSum(1, 2)
writeSum(-1, -2)
writeCountdown(5)
writeMessage("Good bye!")

End

Visual Programming Languages: Scratch

To create subroutines in Scratch, access My Blocks at the side menu, then Make a Block. Set block name to the name of your subroutine. To define parameters, choose Add an input number or text, for values of the types string, integer or real, or Add an input boolean, to make the subroutine receive a relational or logic expression. You can add as many parameters as you need. After adding a parameter, choose a name for it. If you want to remove it, click in the icon of the trash bin (🗑). After defining all parameters, click in OK.

After creating the subroutine's signature, you can insert blocks into it to define its implementation. To use a parameter, you should drag and drop the name of the parameter from the signature to the place it will be used.

Unfortunately, the creation of blocks for subroutines is limited in Scratch. A first limitation is the impossibility to define return values. A second is the impossibility to declare local variables.

As workarounds, you can define global variables and use them in subroutines. It is not an ideal solution, though it is a possible solution for simple program. As the name of every variable must be unique, no other variable can have a name defined for one used in a subroutine. Thus, my recommendation would be prefixing the name with the variable with the name of the subroutine. For instance, you could name a local variable result for the subroutine add() as add_result. With a convention that function_name_result represents the returned value, you can simulate building functions.

Example of using subroutines in Scratch, using the English interface.

As you are using global variables as local variables and returns of subroutines, you must take special care with recursive subroutines. Partial results cannot use the improvised variables (otherwise, the value will be modified in the recursive call, because there exists a single variable shared by all calls). Alternatives include transforming the partial result into a parameter or implementing tail recursion. A more advanced option would be saving local variables at every recursion level in a list (used as a stack), though it would be more complex. Instead of trying to work around the limitations of the language, it is best to use Scratch only for illustrative purposes and using more suitable language for more complex programs. After all, programming languages are tools.

Textual Programming Languages: JavaScript, Python, Lua and GDScript

The previous sections already have provided examples in JavaScript, Python, Lua and GDScript. Thus, the implementation of the subroutines defined using visual resources should be relatively simple at this time.

function write_message(message) {
    console.log(message)
}

function add(x, y) {
    let result = x + y
    return result
}

function write_sum(x, y) {
    write_message(x + " + " + y + " = " + add(x,y))
}

function write_countdown(counter) {
    console.log(counter)
    if (counter > 0) {
        write_countdown(counter - 1)
    }
}

write_message("Hello, my name is Franco!")
write_message(add(1, 2))
write_message(add(-1, -2))
write_sum(1, 2)
write_sum(-1, -2)
write_countdown(5)
write_message("Good bye!")

def write_message(message):
    print(message)

def add(x, y):
    result = x + y
    return result

def write_sum(x, y):
    write_message(str(x) + " + " + str(y) + " = " + str(add(x,y)))

def write_countdown(counter):
    print(counter)
    if (counter > 0):
        write_countdown(counter - 1)

write_message("Hello, my name is Franco!")
write_message(add(1, 2))
write_message(add(-1, -2))
write_sum(1, 2)
write_sum(-1, -2)
write_countdown(5)
write_message("Good bye!")

function write_message(message)
    print(message)
end

function add(x, y)
    local result = x + y
    return result
end

function write_sum(x, y)
    write_message(x .. " + " .. y .. " = " .. add(x,y))
end

function write_countdown(counter)
    print(counter)
    if (counter > 0) then
        write_countdown(counter - 1)
    end
end

write_message("Hello, my name is Franco!")
write_message(add(1, 2))
write_message(add(-1, -2))
write_sum(1, 2)
write_sum(-1, -2)
write_countdown(5)
write_message("Good bye!")

extends Node

func write_message(message):
    print(message)

func add(x, y):
    var result = x + y
    return result

func write_sum(x, y):
    write_message(str(x) + " + " + str(y) + " = " + str(add(x,y)))

func write_countdown(counter):
    print(counter)
    if (counter > 0):
        write_countdown(counter - 1)

func _ready():
    write_message("Hello, my name is Franco!")
    write_message(add(1, 2))
    write_message(add(-1, -2))
    write_sum(1, 2)
    write_sum(-1, -2)
    write_countdown(5)
    write_message("Good bye!")

New Items for Your Inventory

Tools:

Generation of documentation;
Tests;
Refactoring;
Assertions.

Skills:

Creation and use of functions;
Creation and use of procedures;
Recursion.

Concepts:

Modularization;
Subroutines: functions, procedures and methods;
Libraries;
Signature;
Arguments and parameters;
Passing parameters;
First-class function;
Unit test;
Refactoring;
Early return and single entry, single return.

Programming resources:

Subroutines;
Libraries.

Practice

For the Math exercises, it suffices to know how to translate formulas in arithmetic expressions. Do not worry with the symbols. Define variables when necessary and use the required operators. In some cases, you will need conditional structures to avoid errors or to split expressions.

Besides, start crating test cases. When possible, do it even before starting to implement your solution. A important step to solve a problem is to understand it.

Write a procedure that receives a text with an interest as parameter. Write I like {INTEREST}. Next, create some function calls to test your procedure. For instance:
Parameter Expected Result
programming I like programming
computers I like computers
Add a logic value as a new parameter to the procedure of the previous exercise. If the logic value is true True, write I like {INTEREST}. Otherwise, write I do not like {INTEREST}.
Interest Logic Value Expected Result
programming True I like programming
computers False I do not like computers
Modify the previous example. Convert the procedure into a function that returns a string. To combine the text, perform concatenations.
Write functions for the four basic arithmetic operations with the following signatures:
- add(x, y)
- subtract(x, y)
- multiply(multiplicand, multiplier)
- divide(dividend, divisor)
If necessary, create a version for integer numbers and another for real numbers. Test the division with 0 as a divisor (do not allow errors).
Write a function that compares two strings in a case-insensitive way. You can choose to convert the strings to lower case or upper case.
Write a function that calculates the result of a first degree function (linear function).
The result to be calculated corresponds to y (f(x)) in the function. The signature of the function can be linear_function(a, b, x). The parameters and results must be real numbers. For instance, linear(1, 2, 3) = 5, because it would correspond to .
Write a function that calculates the result of a second degree function (quadratic function).
Write a program that solve a second degree equation.
To calculate a second degree equation in the form that admits real roots, the discriminant must not be negative. In this case, the desired result is x.
If , write The equation does not have real roots. Otherwise, write the roots. The calculus of the roots can be performed using the expression:
To do this, you can calculate each root separately:
Write a function that calculates a Math combination.
and are natural numbers, with . The exclamation represents factorial numbers.
To check your solution, you can use the following test cases:
n k Expected Result ()
0 0 1
5 0 1
5 1 5
5 2 10
5 3 10
5 4 5
5 5 1
10 7 120
Negative values should present an error message.
The Fibonacci series is defined as:
Write a subroutine that calculates the Fibonacci number , with being a natural number. To verify if your program is correct, you can consider the following test cases:
n Expected Result ()
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55

Parameter	Expected Result
`programming`	`I like programming`
`computers`	`I like computers`

Interest	Logic Value	Expected Result
`programming`	`True`	`I like programming`
`computers`	`False`	`I do not like computers`

n	k	Expected Result ()
0	0	1
5	0	1
5	1	5
5	2	10
5	3	10
5	4	5
5	5	1
10	7	120

n	Expected Result ()
0	0
1	1
2	1
3	2
4	3
5	5
6	8
7	13
8	21
9	34
10	55

In a subroutine with passage of values by value, what happens if the value of parameter is changed in the definition of the subroutine? Think and try to answer the question. Next, test the following programs and explain the results. Does the swap() method works correctly? Why?

function swap(x, y) {
    let temporary = x
    x = y
    y = x
    console.log("swap() ", x, y)
}

let a = 1
let b = 2
swap(a, b)
console.log(a, b)

let x = 1
let y = 2
swap(x, y)
console.log(x, y)

def swap(x, y):
    temporary = x
    x = y
    y = x
    print("swap() ", x, y)

a = 1
b = 2
swap(a, b)
print(a, b)

x = 1
y = 2
swap(x, y)
print(x, y)

function swap(x, y)
    local temporary = x
    x = y
    y = x
    print("swap() ", x, y)
end

local a = 1
local b = 2
swap(a, b)
print(a, b)

local x = 1
local y = 2
swap(x, y)
print(x, y)

extends Node

func swap(x, y):
    var temporary = x
    x = y
    y = x
    print("swap() ", x, y)

func _ready():
    var a = 1
    var b = 2
    swap(a, b)
    print(a, b)

    var x = 1
    var y = 2
    swap(x, y)
    print(x, y)

In languages that allow passing parameters by reference, it would be possible to define a valid swap() procedure. However, in languages in which the assignment operator can perform assignments to multiple variables at once (such as Python and Lua), it would suffice to do x, y = y, x.

In program languages that do not define an entry point with a specific name, you can create your own main() function or procedure as initial subroutine for your program.
function main() { console.log("Hello, my name is Franco!") } main()
def main(): print("Hello, my name is Franco!") main()
function main() print("Hello, my name is Franco!") end main()
extends Node # GDScript define _init() e _ready(). func _ready(): print("Hello, my name is Franco!")
Instead of adding instructions after the definition of subroutines, you call the proposed subroutine as the program beginning. The chosen name was main(), though you could call it any other name that you wish (for instance, start() or franco()). All program's instructions that are not subroutines could be inside main().
In Python, it is possible to use a conditional structure to transform the function into a true entry point for the program.
```
def main():
    print("Hello, my name is Franco!")

if (__name__ == "__main__"):
    main()
```
What are the advantages that you would cite to define specific entry points?

Next Steps

Subroutines are an important resource of programming languages. Due to its importance, this topic has detailed some techniques to help you to use them in your programs.

Subroutines allow organizing projects, create modular solutions, reuse code, and test solutions with greater ease. With suitable names and good modularity, they can also make it easier to read and understand the code of a project.

Furthermore, recursion allows defining repetitions. However, it is not the only way to do so.

As advanced in conditional structures, there also exists repetition structures (also called loops) to create code that repeats itself based on a condition. They will be the next topic of study.

← Previous:
Learn Programming: Conditional Structures

Next:→
Learn Programming: Repetition Structures (Loops)