Papers/algorithm

using call tree with recursive function

tomato13 2015. 3. 21. 17:48

When you make recursive function or encounter it, your calculation may generate mistakes. 

If you use a call tree, it could be easy way.


For example, let's say about pivonacci number. 

( 1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; )


Then, you can make a function like below. 


fibo(n)

{

if n < 2

{

return 1;

}

else

{

fibo(n-1) + fibo(n-2)

}

}


Let's draw a call tree.


                                                                fibo(7)

                               fibo(6) -------------------------------------    fibo(5)

       fibo(5)  ------------------------fibo(4)                           fibo(4) --------fibo(3)

fibo(4) ----- fibo(3)                      fibo(3)      fibo(2)

.....................