# How to create a trace table for a recursive function

So, I know how to trace an algorithm in discrete mathematics when you have e.g., a for or while loop and then output. But, for some unknown reason, I am lost when it comes to tracing a recursive function calling itself.

def func(n):
if n = 1 then:
func <- 3 + 6
else
func <- (-n) + 2 * func(n - 1)


trace table: func(5)

-------------------------------
|  step  |  n  |  r  | output |
-------------------------------
|   1.   |  5  |  -  |   -    |
|   2.   |  5  |  0  |   -    |


This question, is not concerned with counting, because I've done this already by paper and hand. I even written the method in Python, and received the same output.

def func(n):
r = 0;
if n == 1:
r = 3 + 5
else:
r = (-n) + 2 * func(n-1)
return r

print(func(1)) =  8
print(func(2)) = 14
print(func(3)) = 25
print(func(5)) = 87

• Not very clear... You have to compute $f(5)$? if so compute all values up to argument $5$: $f(1)=9, f(2)=(-2)+2f(1)=-2+18=16, f(3)=(-3)+2f(2)=-3+36=33$ and so on Commented Apr 29, 2022 at 12:26
• Trace table, I have to draw a trace table. But, I have never done one for a recursive function call. I know what it does. Commented Apr 29, 2022 at 12:28

If I'm not mistaken, you are trying to print the results into a trace table like this:

---------------------------
| step |  n  |  r  | output |
---------------------------
|   1  |  1  |  8  |  8   |
|   2  |  2  |  14  |  14   |
|   3  |  3  |  25  |  25   |
|   4  |  4  |  46  |  46   |
|   5  |  5  |  87  |  87   |


def func(n):
r = 0
print("---------------------------")
print("| step |  n  |  r  | output |")
print("---------------------------")

if n == 1:
r = 3 + 5
print("|  ",n ," | ", n ," | ", r," | ", r, "  |")

else:
r = (-n) + 2 * func(n-1)
print("|  ",n ," | ", n ," | ", r," | ", r, "  |")
return r

func(5)