Some questions related to recursion in pseudocode.
I've a question related to pseudocode and trace tables, I have my A level CS papers in a week so I was attempting this question which involved drawing a trace table to a recurring function for returning the values upto a certain number in the Fibonacci sequence.
Function Fib(Num : INTEGER) RETURNS INTEGER
IF Num <= 1 THEN
Result ← Number
ELSE
Result ← Fib(Num - 1) + Fib(Number - 2)
ENDIF
RETURN Result
ENDFUNCTION
So when you run this function you get a trace table like this according to the mark scheme
| Call Number | Function Call | Number | Result | Return Value |
|---|---|---|---|---|
| 1 | Fib(5) | 5 | Fib(4) + Fib(3) | |
| 2 | Fib(4) | 4 | Fib(3) + Fib(2) | |
| 3 | Fib(3) | 3 | Fib(2) + Fib(1) | |
| 4 | Fib(2) | 2 | Fib(1) + Fib(0) | |
| 5 | Fib(1) | 1 | 1 | 1 |
| 6 | Fib(0) | 0 | 0 | 0 |
| (4) | Fib(2) | 2 | 1+0 | 1 |
| (3) | Fib(3) | 3 | 1+1 | 2 |
| (2) | Fib(4) | 4 | 2+1 | 3 |
| (1) | Fib(5) | 5 | 3+2 | 5 |
Can anyone explain to me what is happening in this trace table because I tried to run the same code in python and used python tutor but it gave me a different answer and iterated a lot more times, I have a very basic understanding of python and of pseudocode but this trace feels wrong.
u/Fluid-Article-4193 — 1 day ago