Skip to main content

Software Architecture and Design

Functional Program...

Higher Order ... [python]

This material has been adapted from the "Software Engineering" module of the SABS R³ Center for Doctoral Training.

This material has been adapted from the "Software Engineering" module of the SABS R³ Center for Doctoral Training.

Creative Commons License
This course material was developed as part of UNIVERSE-HPC, which is funded through the SPF ExCALIBUR programme under grant number EP/W035731/1

This course material was developed as part of UNIVERSE-HPC, which is funded through the SPF ExCALIBUR programme under grant number EP/W035731/1

Creative Commons License

Recursion

Recursion

Recursion is one of the common strategies used in Functional Programming. Instead of using loops to iteratively apply an operation, we can express a result in terms of previous results. To do this, the function needs to call itself to get the previous result, this is called recursion.
The following two code examples implement the calculation of a factorial using iteration and recursion, respectively. Recall that the factorial of a number n (denoted by n!) is calculated as the product of integer numbers from 1 to n.
def factorial(n): """Calculate the factorial of a given number. :param int n: The factorial to calculate :return: The resultant factorial """ if n < 0: raise ValueError('Only use non-negative integers.') factorial = 1 for i in range(1, n + 1): # iterate from 1 to n # save intermediate value to use in the next iteration factorial = factorial * i return factorial
Functions in procedural programming are procedures that describe a detailed list of instructions to tell the computer what to do step by step and how to change the state of the program and advance towards the result. They often use iteration to repeat a series of steps. Functional programming, on the other hand, typically uses recursion - an ability of a function to call/repeat itself until a particular condition is reached.
def factorial(n): """Calculate the factorial of a given number. :param int n: The factorial to calculate :return: The resultant factorial """ if n < 0: raise ValueError('Only use non-negative integers.') if n == 0: return 1 # exit from recursion, prevents infinite loops else: return n * factorial(n-1) # recursive call to the same function

Recursion on trees

Recursion is a powerful tool for traversing tree data structures. Consider a tree representing a mathematical expression like 1 + 2 * 3. The tree could have the following structure:
class Node(object): "Generic tree node." def __init__(self, name='root', children=None): self.value = name self.children = children or [] def __repr__(self): return f"Node({self.value}, {self.children})" # + # / \ # 1 * # / \ # 2 3 t = Node('+', [Node('1'), Node('*', [Node('2'), Node('3')])])
Write:
  1. a function that traverses the tree and returns the total number of nodes
  2. a function that traverses the tree and returns the result of the expression

Key Points

  • Recursion is a programming technique where a function calls itself, allowing solutions to problems that can be broken down into smaller subproblems
  • Recursion is a useful approach for calculation and operations on tree data structures.