Das deutsche Python-Forum

Code: Alles auswählen

def fib (n):
    if n<2:
        return n
    else:
        return (fib(n-1) + fib(n-2))

Code: Alles auswählen

        return fib(n-1) + fib(n-2)

Code: Alles auswählen

fib(4)
  fib(3)
    fib(2)
	  fib(1) -> 1
	  +
	  fib(0) -> 1
	  = 2
	+
	fib(1) -> 1
	= 3
  +
  fib(2)
    fib(1) -> 1
	+
	fib(0) -> 1
	= 2
  = 5

Code: Alles auswählen

def fib (n):
    # Rekursionsanker
    if n<2:
        return n

    # Rekursionsschritt
    n_minus_one = fib(n-1)
    n_minus_two = fib(n-2)
    return n_minus_one + n_minus_two

Code: Alles auswählen

sum(fib(2), fib(1)) # sum bildet die Summe der beiden Argumente. Da man aber mit Funktionen schlecht rechnen kann, müssen diese zuerst von Links nach rechts und von innen nach außen aufgelöst, also aufgerufen werden
sum(1, fib(1)) # fib(2) wurde evaluiert und (von der Idee her) das Ergebnis dort eingefügt. Jetzt geht es weiter mit fib(1)
sum(1, 1) # fib(1) wurde ebenfalls evaluiert und das Ergebnis eingesetzt. Jetzt stehen da zwei Ganzzahlen aus denen sum nun die Summe bilden kann.
2

Code: Alles auswählen

sum(fib(3), fib(2)) # Aus fib(3) wird fib f(2) + fib(1)
sum(sum(fib(2), fib(1)), fib(2))) # fib(3) können wir hier von oben übernehmen. Das sind wieder dieselben Schritte, nur diesmal "eingebettet".
sum(sum(1, fib(1)), fib(2))
sum(sum(1, 1), fib(2))
sum(2, fib(2))
sum(2, 1)
3

Code: Alles auswählen

import inspect


def call_stack_depth(stack, function_name):
    return sum(1 for frame_info in stack() if frame_info.function == function_name)


def output(string, depth):
    filler = "|   " * depth
    print(f"{filler}{string}")


def visualize(function):
    def wrapper(*args, **kwargs):
        depth = call_stack_depth(inspect.stack, function.__name__)
        output(f"+ {function.__name__}{args}", depth)
        output("|", depth)
        value = function(*args, **kwargs)
        output(f"{value} <- {function.__name__}{args}", depth)
        output("", depth)
        return value

    return wrapper


@visualize
def fib(n):
    if n < 2:
        return n

    return fib(n - 1) + fib(n - 2)


if __name__ == "__main__":
    fib(5)

"""
Ausgabe:

+ fib(5,)
|
|   + fib(4,)
|   |
|   |   + fib(3,)
|   |   |
|   |   |   + fib(2,)
|   |   |   |
|   |   |   |   + fib(1,)
|   |   |   |   |
|   |   |   |   1 <- fib(1,)
|   |   |   |
|   |   |   |   + fib(0,)
|   |   |   |   |
|   |   |   |   0 <- fib(0,)
|   |   |   |
|   |   |   1 <- fib(2,)
|   |   |
|   |   |   + fib(1,)
|   |   |   |
|   |   |   1 <- fib(1,)
|   |   |
|   |   2 <- fib(3,)
|   |
|   |   + fib(2,)
|   |   |
|   |   |   + fib(1,)
|   |   |   |
|   |   |   1 <- fib(1,)
|   |   |
|   |   |   + fib(0,)
|   |   |   |
|   |   |   0 <- fib(0,)
|   |   |
|   |   1 <- fib(2,)
|   |
|   3 <- fib(4,)
|
|   + fib(3,)
|   |
|   |   + fib(2,)
|   |   |
|   |   |   + fib(1,)
|   |   |   |
|   |   |   1 <- fib(1,)
|   |   |
|   |   |   + fib(0,)
|   |   |   |
|   |   |   0 <- fib(0,)
|   |   |
|   |   1 <- fib(2,)
|   |
|   |   + fib(1,)
|   |   |
|   |   1 <- fib(1,)
|   |
|   2 <- fib(3,)
|
5 <- fib(5,)
"""