💾 Archived View for hackersphere.space › ~willowf › gemlog › csci-lecture-notes › 2023-10-02.gmi captured on 2023-11-14 at 08:21:22. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

Recursion

Return to notes index

Types of recursion

Two types of recursive calls: Direct and Indirect
Two types of recursive functions: Linear and Nonlinear
A direct call is where the recursive function directly calls itself.
An indirect call is where the call graph is a cycle between multiple different functions.
A linear recursive algorithm is one whose call graph is a straight line, i.e. it never calls itself more than once.
A nonlinear recursive algorithm is one whose call graph branches, i.e. in some cases it calls itself more than once.

Three main rules of recursion

Base case: There must be a stopping point for recursion.
General case: A function is not recursive unless it calls itself.
Recursive case: Each call should get the recursive function closer to the base case.

Implicatons of stack-based recursion for big-O complexity

Recursive functions can be surprisingly complex.
The fact that stack frames take up space means that recursion can increase the space complexity of an algorithm.
For example, the following nonlinear recursive function has O(2^n) time complexity and O(n) space complexity:

def fib(n):
    match n:
        case 0:
            return 0
        case 1:
            return 1
        case _:
            return fib(n-1) + fib(n-2)

Whereas this non-recursive function has O(n) time complexity and O(1) space complexity:

def fib(n):
    f1, f2 = 0, 1
    for i in range(n):
        f1, f2 = f2, f1 + f2
    return f1

And this linear recursive function has O(n) time complexity and O(n) space complexity:

def fib(n, f1=0, f2=1):
    match n:
        case 0:
            return f1
        case 1:
            return f2
        case _:
            return fib(n-1, f2, f1+f2)