Page 400 - Computer science 868 Class 12
P. 400
11.1 CONCEPT OF RECURSION
n
Let us explain the concept with a simple example. Suppose we want to find a . If we design a loop, then we define a
variable whose value changes from 1 to n and multiplying the term with the product ‘n’ number of times, produces
the required result like
p = a × a × a × a × ........... n times.
Or we can define it in a different way as
F(1) = a
F(2) = a × F(1)
F(3) = a × F(2)
....
So we conclude F(n) = a × F(n - 1 + 1)
We find that in each step we are calling the same function with a different argument until we reach a point, where we
stop calling the function. This step is the base case. The other steps where we are calling the same function but with
different argument is called the recursive case.
So we conclude that a recursive function is made up of two components:
• The condition where the function stops calling itself. This is a very important part of recursion
Base case
construct otherwise the function will call itself infinitely until the program crashes
Recursive • The case in which the function calls itself repeatedly with changed value of argument
case
Recursion works on the principle of Stack. Stack has only one end – the top. Both insertion and deletion take place at
the top of the stack. Thus recursion works on LIFO (Last In First Out ) principle. When a recursive method is called, the
computer creates a new stack of frames and places it at the top of stack. When the base case is reached, these frames
are removed from top one after another until it is empty.
Recursion has already been covered in details in Chapter 12 of class XI book. Let us do a small revision tour before
attempting programs with higher complexity.
Question 1: The following is a part of some class. What will be the output of the function mymethod( ) when the value
of counter is equal to 3? Show the dry run/working. [ISC 2011]
void mymethod(int counter)
{
if(counter==0)
System.out.println(" ");
else
{
System.out.println("Hello "+ counter);
mymethod(--counter);
System.out.println(" "+ counter);
}
}
398398 Touchpad Computer Science-XII

