the fibonacci sequence is the sequence of numbers it starts with two and successive numbers are the sum of the previous two one way to compute the nth fibonacci value is to use loop that produces successive terms of the sequence in order to compute the next fibonacci numberwe always need to keep track of the previous two we can use two variablescurr and prevto keep track these values then we just need loop that adds these together to get the next value at that pointthe old value of curr becomes the new value of prev here is one way to do it in pythondef loopfib( )returns the nth fibonacci number curr prev for in range( - )currprev curr+prevcurr return curr used simultaneous assignment to compute the next values of curr and prev in single step notice that the loop only goes around timesbecause the first two values have already been assigned and do not require an addition the fibonacci sequence also has an elegant recursive definition ib( if ib( ib( otherwise we can turn this recursive definition directly into recursive function def fib( )if return elsereturn fib( - fib( - this function obeys the rules that we've set out the recursion is always on smaller valuesand we have identified some non-recursive base cases thereforethis function will worksort of it turns out that this is horribly inefficient algorithm while our looping version can easily compute results for very large values of (loopfib( is almost instantaneous on my computer)the recursive version is useful only up to around the problem with this recursive formulation of the fibonacci function is that it performs lots of duplicate computations figure shows diagram of the computations that are performed to compute fib( notice that fib( is calculated twicefib( is calculated three timesfib( four timesetc if you start with larger numberyou can see how this redundancy really piles upso what does this tell usrecursion is just one more tool in your problem-solving arsenal sometimes recursive solution is good oneeither because it is more elegant or more efficient