Implementation of recursive calls

- Static Vs Dynamic allocation of activation records

Whenever a procedure is called, all the relevant information about the procedure such as program counter, values of a variables/registers is stored in an activation record.

- Static: Fortran. Only one copy of activation record.

- Dynamic: Algol-like languages.

- Activation records are created at the time of the call to subprogram.

- There is new instantiation of all the local variables.

- Maintained on the stack.

- Stack is ideal for such things.

• Recursive definition
  • The definition of a term that uses the term being defined.
  • fib(n) = fib(n-1)+fib(n-2)
  • fibonacci numbers are defined in terms of fibaonacci numbers
  • The recursive definitions are always supplemented by non-recursive special case definitions
  • fib(1)=1 and fib(2)=1
  • with these special cases the recursion can terminate and we get a complete definition
  • Factorial
  • n! = 1*2*3*....*n;
  • n! = n*(n-1)!
  • The second definition is recursive
• Both Fibonacci and Factorial definitions look very compact using recursion
• Corresponding C++ functions also are readable as opposed to their iterative equivalents. See files fact*.cpp and fib*.cpp
• These are bad examples of recursion. We can use the recursion trees to verify this

factorial(5)

|

factorial(4)

|

factorial(3)

|

factorial(2)

|

factorial(1)

• The recursion tree is a chain. That means evaluation of factorial(5) is going to result in five function calls. These call can be expensive. As opposed to that iterative version will mean a single function call. The time requirement for both is still linear.
• If the recursive tree is a chain and both iterative and recursive are equally readable, use iterative version.
• For fibonacci, the recursion tree will look like this

• Time requirement O(2^n) - recursive
• Iterative time requirement O(n)
• If recursion tree shows duplication of work, don't use recursion
• Any problem with a recursive solution can also be solved iteratively.

Tower of Hanoi

• Three towers a, b, and c. We want to move 64 disks from tower a to c.
  • Allowed to move one disk at a time
  • You cannot place larger disk on top of smaller disk
• When all the disks are moved from tower a to tower c, the world will come to an end
• We can picture the problem with two or three disks very easily
• Difficult to come up with a generic procedure for any number of disks
• Recursive algorithm
• Problem move n disks from orig to dest using temp
• If n == 1 then trivially move disk 1 from orig to dest
• Else
  • Move n-1 disks from orig to temp using dest
  • trivially move disk n from orig to dest
  • Move n-1 disks from temp to dest using orig
• See Hanoi.pas
• Complete the following recursion tree and write down the output compare it to the output from the program hanoi.pas