Transcript Recursion

Recursion
Lakshmish Ramaswamy
Basics of Recursion
• A recursive method makes a call to itself
directly or indirectly
• Is this not endless circular logic?
– Call is for a simpler instance
• Several real-world applications are recursive
– Dictionary lookup for definitions
– Scanning files on a computer
– Computer languages
A Simple Example
• Calculate sum of first N integers (S(N))
• We know S(1) = 1
• S(N) can be expressed as S(N) = S(N-1) + N
– S(2) = 2 + S(1)
– S(3) = S(2) + 3
– S(N) = N(N+1)/2 <---- Closed form
• Closed form are often complex
• Recursive expressions might be simpler
Recursive Method for S(N)
Points to Note
• Function calls a clone of itself (note the
difference in parameters)
• Only one clone is active at any instance
– Computer does all the book keeping for you
• Base case – Instance that can be solved
without recursion
– S(1) is the base case
• Recursive call should make progress
towards base case
Two Rules
• Always have at least one base case
solved without recursion
• Any recursive call should make progress
towards base case
Second Example
• Printing numbers in any base
• Simpler case – Printing number in decimal
form
– No method that can print an integer
– Method that can print a single character
– Digits are treated as characters
• print(2457) can be expressed as print(245)
followed by printing 7 (via character
printing method)
Decimal Printing Method
• Identify the base condition?
• How is the progress done?
Printing Number in any Base
• Exception if base > 16
• Infinite loop if base is 1
– Notice identical call to the method (No progress)
Robust Implementation
How is Recursion Supported
• Method invocation requires bookkeeping
– Recursion is no different (may be a special
case)
• Activation records for implementing
methods
– Activation records hold important information
like parameter values & local variables
Stacks for Activation Records
• Stack is a good data structure for reversing
order
– First-In-Last-Out paradigm
• Why stacks?
– Notice that methods return in reverse order of
invocation
• Activation record at top is that of currently active
method
– When a method is called, its activation record is
pushed on the stack
– Top record is popped when the method returns
Stacks and Recursive Methods
• Each method invocation results in an activation
record
• The base case is the last one to be pushed in
and the first one to pop out
Fibonacci Numbers
• Definition
– FN = FN-1 + FN-2
– F1 = 1
– F0 = 0
• Very interesting properties
– Sum of first N Fibonacci numbers < FN+2
– Sum of squares of two consecutive Fibonacci
numbers is also a Fibonacci number
• Natural recursive implementation
Simple but Inefficient
Implementation
What is the Problem?
• Each call to fib(n-1) and fib(n-2) results in calling
fib(n-3)
• Keeps getting worse – Observe how many times
F2, F1 and F0 are called
• Lesson – Avoid duplicate work of solving same
instance in separate duplicate calls
Factorial Computation