Unit 5. Assessment Review

 5장의 평가 문제에서는 Recursion의 구조, 불변 데이터와 Recursion을 왜 사용하는지에 대해 피드백합니다.

Q4. List the two ways in which recursion is used in Computer Science.

 Recursion is used in Computer Science to both describe a problem(that is, the requirements) and to design a solution to that problem(D & C)

Q5. A recursive function defined in two parts.  Name the two parts.

 The two parts are the base case(s) and the recursive step(s).  In the base case, a function output value is computed directly from input values.  In the recursive steps, a function value is computed by applying the function to reduced input values that are closer to the input value(s) used in the base case.

Q6. Define tail recursion

 A recursion function is one in which the call to itself is 'in the tail position' - that is, in the last statement of the function.  As a consequence, when the function finishes it only has to return value; no deferred operations are built up and the return address does not to have to be saved on the stack.  Tail recursion can be implemented by the programmer or compiler by using iteration and thus saving space and time.

발췌 : wikipedia

 Tail-recursive functions are functions in which all recursive calls are tail calls and hence do not build up any deferred operations. For example, the gcd function (shown again below) is tail-recursive. In contrast, the factorial function (also below) is not tail-recursive; because its recursive call is not in tail position, it builds up deferred multiplication operations that must be performed after the final recursive call completes. With a compiler or interpreter that treats tail-recursive calls as jumps rather than function calls, a tail-recursive function such as gcd will execute using constant space. Thus the program is essentially iterative, equivalent to using imperative language control structures like the "for" and "while" loops.

1 2 3 4 5 6 def gcd(x, y):     if y == 0:         return x     else:         return gcd(y, x%y) print gcd(1000, 3) cs

1 2 3 4 5 def fact(n):     if n==0:         return 1     else:         return n*fact(n-1) cs

 The significance of tail recursion is that when making a tail-recursive call (or any tail call), the caller's return position need not be saved on the call stack; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, in languages that recognize this property of tail calls, tail recursion saves both space and time.

요약 : 꼬리 재귀는 return에서 어떠한 operation도 사용하지 않고 오직 function을 호출 매개변수에만 변화를 준다.  위의 factorial 함수와 같은 일반 재귀는 recursive step부에 operation을 사용하게 되면 후에 호출부에 저장된 스택을 완료하는 절차가 남게된다.  gcd 함수와 같은 꼬리 재귀는 어떠한 operation도 사용하지 않았으므로 저장된 스택을 완료하는 절차가 없어 imperative programming에서의 반복문의 기능과 동일한 역할을 하게 된다.

Q7. List three reasons to use recursion.

1. the program is naturally recursive
2. the problem is naturally recursive
3. to take advantage of immutability of data: A pure recursive function has no side effect.  It's output value only depends on its input parameters and it does not change any other parts of the program. 
   

Q8. What does 'immutability of data' mean in the context of recursive functions?

 Immutability of data means that the data is not changed.  A function's data consist of parameters, local variables, and a return value, or, respectively, input data, variables used by function for computation, and output data.  In other words, a pure function has no sied effects and it does not mutate, or change data, outside the program.

Q9. Name several common problems that are solved by Divide and Conquar algorithms, where the 'dividing' of the problem is done by recursion.

 Sorting and Searching are common problems that are solved by Divide and Conquar algorithms using recursion.  For example, binary search is an efficient recursive algorithm of complexity log n.  Merge sort is an efficient recursive algorithm of complexity n log n for sorting a list, which can then be searched using a binary search.

Q10. A recursive implementation can be replaced by an implementation using iteration.  What is the tradeoff between the two implementation?

 If the problem or data is naturally recursive, a recursive implementation will closely match the design.  An iterative implementation may be harder to understand and may add complexity, since iteration may mutate data.  Recall that an advantage of recursion is the immutability of data.  Further, there is a tradeoff of time and space.  A recursive implementation can use a large amount of space on the call stack, which may save a significant amount of execution time.  An iterative implementation uses less space, but at a cost of more time.  These advantages and tradeoffs need to be assessed in the particular context of each problem, including their program requirements, context, resources, environment, and number of uses.