Examples of tail recursion, but Python fails at it

README.md

To see the different call patterns:

================================================================================
factorial_recursive:
BEGIN: (5)
  BEGIN: (4)
    BEGIN: (3)
      BEGIN: (2)
        BEGIN: (1)
          END: (1) -> 1
        END: (2) -> 2
      END: (3) -> 6
    END: (4) -> 24
  END: (5) -> 120
================================================================================
factorial_tail_recursive:
BEGIN: (5)
  BEGIN: (4, partial=5)
    BEGIN: (3, partial=20)
      BEGIN: (2, partial=60)
        BEGIN: (1, partial=120)
          BEGIN: (0, partial=120)
            END: (0, partial=120) -> 120
          END: (1, partial=120) -> 120
        END: (2, partial=60) -> 120
      END: (3, partial=20) -> 120
    END: (4, partial=5) -> 120
  END: (5) -> 120
================================================================================
factorial_loop:
BEGIN: (5)
  END: (5) -> 120
================================================================================
fibonacci_recursive:
BEGIN: (6)
  BEGIN: (5)
    BEGIN: (4)
      BEGIN: (3)
        BEGIN: (2)
          BEGIN: (1)
            END: (1) -> 1
          BEGIN: (0)
            END: (0) -> 1
          END: (2) -> 2
        BEGIN: (1)
          END: (1) -> 1
        END: (3) -> 3
      BEGIN: (2)
        BEGIN: (1)
          END: (1) -> 1
        BEGIN: (0)
          END: (0) -> 1
        END: (2) -> 2
      END: (4) -> 5
    BEGIN: (3)
      BEGIN: (2)
        BEGIN: (1)
          END: (1) -> 1
        BEGIN: (0)
          END: (0) -> 1
        END: (2) -> 2
      BEGIN: (1)
        END: (1) -> 1
      END: (3) -> 3
    END: (5) -> 8
  BEGIN: (4)
    BEGIN: (3)
      BEGIN: (2)
        BEGIN: (1)
          END: (1) -> 1
        BEGIN: (0)
          END: (0) -> 1
        END: (2) -> 2
      BEGIN: (1)
        END: (1) -> 1
      END: (3) -> 3
    BEGIN: (2)
      BEGIN: (1)
        END: (1) -> 1
      BEGIN: (0)
        END: (0) -> 1
      END: (2) -> 2
    END: (4) -> 5
  END: (6) -> 13
================================================================================
fibonacci_tail_recursive:
BEGIN: (6)
  BEGIN: (5, previous=1, current=1)
    BEGIN: (4, previous=1, current=2)
      BEGIN: (3, previous=2, current=3)
        BEGIN: (2, previous=3, current=5)
          BEGIN: (1, previous=5, current=8)
            BEGIN: (0, previous=8, current=13)
              END: (0, previous=8, current=13) -> 13
            END: (1, previous=5, current=8) -> 13
          END: (2, previous=3, current=5) -> 13
        END: (3, previous=2, current=3) -> 13
      END: (4, previous=1, current=2) -> 13
    END: (5, previous=1, current=1) -> 13
  END: (6) -> 13
================================================================================
fibonacci_loop:
BEGIN: (6)
  END: (6) -> 13

assembly.O0.txt

# https://godbolt.org/z/N2RPeF
factorial(int, int):
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     DWORD PTR [rbp-4], edi
        mov     DWORD PTR [rbp-8], esi
        cmp     DWORD PTR [rbp-4], 1
        jg      .L2
        mov     eax, DWORD PTR [rbp-8]
        jmp     .L3
.L2:
        mov     eax, DWORD PTR [rbp-8]
        imul    eax, DWORD PTR [rbp-4]
        mov     DWORD PTR [rbp-8], eax
        mov     eax, DWORD PTR [rbp-4]
        lea     edx, [rax-1]
        mov     eax, DWORD PTR [rbp-8]
        mov     esi, eax
        mov     edi, edx
        call    factorial(int, int)
        nop
.L3:
        leave
        ret

assembly.O2.txt

# https://godbolt.org/z/FC03dq
factorial(int, int):
        mov     eax, esi
        cmp     edi, 1
        jle     .L5
.L2:
        imul    eax, edi
        sub     edi, 1
        cmp     edi, 1
        jne     .L2
.L5:
        ret

how_recursive.c

// /usr/local/Cellar/gcc/8.2.0/bin/gcc-8 -O0 -c how_recursive.c -o how_recursive.O0.o
// /usr/local/Cellar/gcc/8.2.0/bin/gcc-8 -O2 -c how_recursive.c -o how_recursive.O2.o
int factorial(int n, int partial)
{
    if (n < 2)
    {
        return partial;
    }
    else
    {
        partial = n * partial;
        return factorial(n - 1, partial);
    }
}

how_recursive.O0.o

how_recursive.O2.o

how_recursive.py

import functools


SEPARATOR = "=" * 80


def pretty_args(args, kwargs):
    all_args = ""
    if args:
        all_args = ", ".join(str(arg) for arg in args)
    if kwargs:
        pretty_kwargs = ", ".join(
            "{}={}".format(name, value) for name, value in kwargs.items()
        )
        if all_args:
            all_args = "{}, {}".format(all_args, pretty_kwargs)
        else:
            all_args = pretty_kwargs
    return all_args


def get_prefix(kwargs):
    return kwargs.pop("prefix", "")


def set_prefix(prefix, kwargs):
    # "Smuggle" in a new value.
    kwargs["prefix"] = "  " + prefix


def show_stack(func):
    @functools.wraps(func)
    def wrapped(*args, **kwargs):
        prefix = get_prefix(kwargs)
        all_args = pretty_args(args, kwargs)
        print("{}BEGIN: ({})".format(prefix, all_args))
        set_prefix(prefix, kwargs)
        result = func(*args, **kwargs)
        print("{}  END: ({}) -> {}".format(prefix, all_args, result))
        return result

    return wrapped


@show_stack
def factorial_recursive(n, **kwargs):
    if n < 2:
        return 1
    else:
        return n * factorial_recursive(n - 1, **kwargs)


@show_stack
def factorial_tail_recursive(n, partial=1, **kwargs):
    if n == 0:
        return partial
    else:
        return factorial_tail_recursive(n - 1, partial=n * partial, **kwargs)


@show_stack
def factorial_loop(n, **kwargs):
    partial = 1
    for k in range(n, 0, -1):
        partial = k * partial
    return partial


@show_stack
def fibonacci_recursive(n, **kwargs):
    if n == 0 or n == 1:
        return 1
    else:
        return fibonacci_recursive(n - 1, **kwargs) + fibonacci_recursive(
            n - 2, **kwargs
        )


@show_stack
def fibonacci_tail_recursive(n, previous=0, current=1, **kwargs):
    if n == 0:
        return current
    else:
        return fibonacci_tail_recursive(
            n - 1, previous=current, current=previous + current, **kwargs
        )


@show_stack
def fibonacci_loop(n, **kwargs):
    previous, current = 0, 1
    for _ in range(n):
        previous, current = current, previous + current
    return current


def main():
    print(SEPARATOR)
    print("factorial_recursive:")
    assert factorial_recursive(5) == 120
    print(SEPARATOR)
    print("factorial_tail_recursive:")
    assert factorial_tail_recursive(5) == 120
    print(SEPARATOR)
    print("factorial_loop:")
    assert factorial_loop(5) == 120

    print(SEPARATOR)
    print("fibonacci_recursive:")
    assert fibonacci_recursive(6) == 13
    print(SEPARATOR)
    print("fibonacci_tail_recursive:")
    assert fibonacci_tail_recursive(6) == 13
    print(SEPARATOR)
    print("fibonacci_loop:")
    assert fibonacci_loop(6) == 13


if __name__ == "__main__":
    main()