---

Recursion

from typing import Any, Optional

Fibonacci

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) for n > 1

Time complexity: O(2^n) - Exponential time complexity due to repeated calculations of the same Fibonacci numbers.

Space complexity: O(n) - The maximum depth of the recursion is n, which occurs when calculating F(n).

def f(n):
    if n <= 1:
        return n
    return f(n - 1) + f(n - 2)


f(12)

144

Reverse a singly linked list

• O(n) time complexity
• O(n) space complexity due to the recursive call stack.

class Node:
    def __init__(self, value: Any, next: Optional["Node"] = None) -> None:
        self.value = value
        self.next = next

    def __str__(self) -> str:
        return str(self.value)


head = Node(1)
a = Node(2)
b = Node(3)
c = Node(4)

head.next = a
a.next = b
b.next = c

Reverse function

def reverse(node: Node) -> None:
    if not node:
        return
    reverse(node.next)
    print(node)


reverse(head)

4

3

2

1