Question about recursion and dynamic programming

Thread Starter

Werapon Pat

Joined Jan 14, 2018
35
suppose that I have a fibonacci function like this using recursion

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

when it comes to fib(n-1)+fib(n-2), I wonder which function will be computed first fib(n-1) or fib(n-2) or they both are computed at the same time.
and if it's fib(5)

hi.jpg
Does the process go like (a,b,d,h,i,e,c,f,g)
actually I just learn about dynamic programming and I just want to know when the memo takes the value while the function's executed.
please let me know if this question makes you confuse because my english isn't good, and i'll try explain more.
 
Last edited:

Papabravo

Joined Feb 24, 2006
14,664
It depends on the compiler, and there is no a priori way to know. The value of 'n' passed to the function is the same for the evaluations of (n-1) an (n-2) and the value of (n-1)-(n-2) is identically 1 for all n >0. The only way they could be computed at the same time is with a multiple processor architecture. You would never know about this at the compiler level.
 

WBahn

Joined Mar 31, 2012
26,279
It depends on both the language specification (is this Python?) and the compiler. The language specification will dictate the order in which something must be done, but leave other things up to the compiler implementer to decide. In most cases the code will be generated so that one term in an expression will be fully evaluated before evaluation starts on another term. But unless the language specifies order of evaluation of terms and factors, many compilers will evaluate terms from right to left because this is a fairly natural way to develop the parser.
 
Top