CMPT 120 Lecture Notes - Lecture 22: Divisor

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 120
• Professor: Liaqat Ali

Document Summary

Less efficient: entails function calling overhead that is not necessary with a loop. Usually a solution using a loop is more evident than a recursive solution. Some problems are more easily solved with recursion than with a loop. Example: fibonacci, where the mathematical definition lends itself to recursion. Summing a range of list elements with recursion. Function receives a list containing range of elements to be summed, index of starting item in the range, and index of ending item in the range. Base case: if start index > end index return 0. Recursive case: return current_number + sum(list, start+1, end) Fibonacci series: has two base cases if n = 0 then fib(n) = 0. If n = 1 then fib(n) = 1 if n > 1 then fib(n) = fib(n-1) + fib(n-2) Calculation of the greatest common divisor (gcd) of two positive integers. If x can be evenly divided by y, then. Otherwise, gcd(x,y) = gcd(y, remainder of x/y)