Recursion
In mathematical logic and computer science, a function or procedure is
said to be a recursive routine if it is defined in terms of itself.
A recursive function is made of the
1. Base case – i.e 0! =1
2. The general case n! = n x (n-1)!
The general case must move towards the base case.
4! = 4 x (4-1)! = 4 x 3!
3! = 3 x (3-1)! = 3 x 2!
2! = 2 x (2-1)! = 2 x 1!
1! = 1 x (1-1)! = 1 x 0!
Recursion
Recursive solutions have a base case and a general case. The base case gives a
result without involving the general case. The general case is defined in terms of the
definition itself. It is very important that the general case must come closer to the
base case with each recursion, for any starting point.
Base case: an explicit solution to a recursive function
General case: a definition of a recursive function in terms of itself
Recursion
Coding the factorial function
Iterative Factorial function using a loop :
FUNCTION Factorial (n : INTEGER) RETURNS INTEGER
Result 1
FOR i 1 TO n
Result Result* i
END FOR
RETURN Result
ENDFUNCTION
Recursion
Recursive Factorial function
FUNCTION Factorial (n :INTEGER) RETURNS INTEGER
IF n = 0 THEN
Result 1
ELSE
Result n * Factorial (n - 1)
END IF
RETURN Result
ENDFUNCTION
Recursion
When writing a recursive subroutine, there are three rules you must
observe.
A recursive subroutine must:
• have a base case
• have a general case
• reach the base case after a finite number of calls to itself.
Task
Write program code to implement the recursive algorithm for the
Factorial function.
What happens when the function is called with Factorial (-2)?
Which rule is not satisfied?
Task
Coding a recursive procedure
Consider a procedure to count down from a given integer. We can write the solution as an iterative
algorithm:
PROCEDURE CountDownFrom(n : INTEGER)
FOR i n DOWNTO 0
OUTPUT i
ENDFOR
END PROCEDURE
We can also write the solution as a recursive algorithm. Consider what happens after the first value
has been output. The remaining numbers follow the same pattern of counting down from the next
smaller value. The base case is when n reaches 0. 0 will be output but no further numbers. The
general case is outputting n and then counting down from (n-1).
Task
Coding a recursive procedure
This can be written using pseudocode:
PROCEDURE CountDownFrom (n : INTEGER)
OUTPUT n
IF n > 0 THEN
CALL CountDownFrom(n-1)
ENDIF
END PROCEDURE
Task
Coding a recursive procedure
This can be written using pseudocode:
PROCEDURE CountDownFrom (n : INTEGER)
OUTPUT n
IF n > 0 THEN
CALL CountDownFrom(n-1)
Tracing a recursive subroutine
ENDIF
END PROCEDURE
Task
This can be written using pseudocode:
PROCEDURE CountDownFrom (n : INTEGER)
OUTPUT n
IF n > 0 THEN
CALL CountDownFrom(n-1)
ENDIF
OUTPUT n
END PROCEDURE
statements after CALL countUpTo(n-1) are not executed until control returns to this statement as the
recursive calls unwind. What is the effect of moving the OUTPUT statement to the end of the
procedure?
Tracing a recursive function
A recursive function has a statement after the recursive ca ll to itself: the RETURN statement.
Again we show what happens when the recursive ca lls unwind by fi lling in more rows in the
trace table. Let's consider the factorial function again .
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 THEN
Result 1
ELSE
Result .... n * Factorial (n-1)
ENDIF
RETURN Result
END FUNCTION
Tracing a recursive function
Benefits and drawbacks of recursion
Recursive solutions are often more elegant and use less
program code than iterative solutions. However,
repeated recursive calls can carry large overheads in
terms of memory usage and processor time For
example, the procedure call countDownFrom(100) will
require 100 stack frames before it completes.