XII CS : Recursion

 RECURSION

 
Definition : 
Recursion is the process in which a function calls a copy of itself .
The function which calls itself is called recursive function, and such
function calls are called recursive calls.

Recursion is one of the most powerful tools in a programming language. 
it is a function calling itself again and again. 
it is a method in which a function calls itself one or more times in its body

Note : Condition must be specified to stop recursion; 
          otherwise it will lead to an infinite process


Advantages of using Recursion:
 i. Recursion is more elegant and requires a lesser number of variables 
    which makes the program short and clean.

 ii. Recursion can lead to more readable and efficient algorithm descriptions


Disadvantages of using Recursion:
 i. It slowing down execution time. 

ii. If recursion is too deep, then there is a danger of running out of space on 
   the stack and ultimately program crashes.

iii. It is comparatively difficult to think of the logic of a recursive function.
 
iv. It also sometimes becomes difficult to debug a recursive code 



Consider the example given below This program is to print numbers up to 10. 
We will pass starting number say n and this function will print Numbers from n to 9 


1. def rec_fun(n): # Function Definition 
2. if n>=10:
3. return
4. else:
5. print(n)
6. rec_fun(n+1)
7. rec_fun(5) # Function Call


In above example function is calling itself (line no.6 )


In line 7, we have called the recursive function rec_fun() with parameter 5.







How Recursion works:
Recursion is implemented by dividing the recursive problem into two parts. 
A useful recursive function usually consists of the following parts:
Terminating Part: (for the smallest possible problem) When the function returns a value directly.
Recursive Part: Which contains one of the more recursive calls on smaller parts of the problem.

Simple Programs using recursion:

#To calculate power of an inputted number
def power(x,n):
     if n==0:
        return 1
    else:
        return x*power(x,n-1)
a=2
print(power(a,4))

Output:
16


#To find the sum of first 'n' natural numbers using Recursion

def recur_sum(n):
     if n<=1:
       return n
    else:
       return n+recur_sum(n-1)
num=int(input("Enter a number :"))
if num<0:
     print("Enter a positive number")
else:
     print("The sum is :", recur_sum(num))

OUTPUT:
Enter a number : 6
The sum is : 21


# Function to display Fibonacci Series using Recursion

def recur_fibo(n):
     if n<=1:
       return n
     else:
       return (recur_fibo(n-1) + recur_fibo(n-2))
nterms= int(input("how many terms ....."))
print("Fibonacci Series is...")
for i in range (nterms):
    print (recur_fibo(i))

OUTPUT:
how many terms...: 10
Fibonacci Series is...:
0
1
1
2
3
5
8
13
21
34
Explanation: 
A Fibonacci series is a sequence of integers in which the first two terms are 0 and 1. 
All other terms of the sequence are obtained by adding their preceding two numbers. The above program
takes the number of terms and determines  the Fibonacci series using recursion up to n terms.

#Function to find the Factorial of a number using Recursion

def recur_factorial(n):
     if n==1:
         return n
     else:
         return n*recur_factorial(n-1)
num=int(input(Enter a number :"))
if num<0:
     print("Sorry, factorial for a negative number does not exist")
elif num==0:
     print("The factorial of 0 is 1")
else:
     print("The factorial of ", num,"is",recur_factorial(num))

OUTPUT:
Enter a number : 5
The factorial of 5 is 120

RECURSIVE PROGRAM TO IMPLEMENT BINARY SEARCH IN LIST/ARRAY

In binary search technique , the entire sequence of numbers (list/array) is divided into two parts and 
the middle element of list/array is extracted. This technique is also known as "Divide and conquer' technique.
To search an element, say "Val' in a sorted array (suppose in ascending order), the val is compared
with the middle element first. If the searched value is equal to the middle value, then the index
number and position number of this element is returned. If the val is greater than the middle element,
 the second half of the array becomes the new segment to be traversed, if the val is less than the middle element, 
the first half becomes the new segment to be scanned.The same process is repeated until val is found or 
the segment is reduced to the single element and still val is not found (in case of an unsuccessful search)

For example:
index:   0   1   2  3    4    5    6    7
Value : 10 15 25 30  42  55  67  89

Low value: 10
Mid value: 30
High Value: 89

if searched value is 42, then 42>mid value(30)
if searched value is 30, then 30=mid value (30)

#    PROGRAM FOR BINARY SEARCH IN A LIST/ARRAY USING RECURSION

def binary_search(list, low, high,val):
  if(high<low):
    return None
  else:
    midval= low + (high - low) // 2
#compare the search item with middle most value
  if list[midval]>val:
    return binary_search(list, low,midval-1,val)
  elif list[midval]< val:
    return binary_search (list, midval+1, high,val)
  else:
    return midval
list=[5,11,22,36,99,101]
print(binary_search (list,0,5,36))
print (binary_search (list,0,5,100))

OUTPUT:
3
None

Recursion V/S Iteration

Recursion and iteration are inter-realted concepts. however, even for problems 
that can be handled equally well using both the techniques, there is a subtle difference
in the manner loops and method calls are handled by a compiler or interpreter.
When a loop is executed repeatedly, it uses the same memory locations for variables and 
repeats the same unit of code. on the other hand , recursion, instead of repeating the same unit of code
and using the same memory locations for variables, allocates fresh memory space for each 
recursive call.