3
$\begingroup$

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
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Commented Apr 29, 2022 at 12:26
  • $\begingroup$ 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. $\endgroup$ Commented Apr 29, 2022 at 12:28

1 Answer 1

1
$\begingroup$

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   |

Please feel free

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)
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .