Skip to main content

Recursion

                                                 Recursion 

 A function calling itself is called recursion 
      • There must be a base condition that will terminate the recursion, otherwise it will go into infinite loop.
 Syntax : 

Type fun( param ) {
 if( < base condition > ) {
 1………. 2.
 fun( param ) 
3………. } 
} 


 • Once the functions are executed and the end result is obtained, then it traces back to the previous functions and terminates it until all the calls are closed and terminated. 
• Printing of function can be done on calling time or returning time.

Head Recursion 

#include <stdio.h>
void fun(int n) {
 if(n>0) {
 fun(n-1); 
 printf("%d ",n);
 } 
} 
int main() {
 int x=3;
 fun(x); 
 return 0; 
} 
Output -: 1 2 3
call fun(3)
call fun(2)
call fun(1)
call fun(0)
print 1
print 2
print 3


Tail Recursion 

#include <stdio.h>
 void fun(int n) { 
 if(n>0) { 
 printf("%d ",n);
 fun(n-1); 
 }
 }
 int main() { 
 int x=3;
 fun(x); 
 return 0 ;
 }

Output -: 3 2 1
print 3
call fun(2)
print 2
call fun(1)
print 1
call fun(0)
terminate

  • Recursion is also just like loop. But the difference is a loop will have only ascending phase or descending, but the recursion will have ascending as well as descending phase.
  • Recursive functions are memory consuming.

#include <stdio.h>
void fun(int n) { 
 if(n>0) { 
 printf("%d ",n);
 fun(n-1); 
 printf("%d ",n);
 }
 }
 int main() { 
 int x=3;
 fun(x); 
 return 0 ;
 }

output-:3 2 1 1 2 3
 time complexity O(n) and space complexity O(n)


                1                n=0
T(n) =
                T(n-1)+1   n>0

Solution-:

T(n)=T(n-1)+1 --------------------------------(1)

if put n=n-1

T(n-1)=T(n-1-1)+1
T(n-1)=T(n-2)+1 ------------------------------(2)
put the value of T(n-1) into first equation
T(n)=T(n-2)+1+1
T(n)=T(n-2)+2 --------------------------------(3)
put the value of n=n-1 in the third equation, we got the equation
T(n-1)=T(n-1-2)+2
T(n-1)=T(n-3)+2
put the value of T(n-1) into first equation
T(n)=T(n-3)+2+1
T(n)=T(n-3)+3
:
:
:
:
:
T(n)=T(n-k)+k           Assume that n-k=0  so n=k
n is replaced with k
T(n)=T(n-n)+n
T(n)=T(0) +n
T(n)=n+1    ---------------------O(n)


Popular posts from this blog

Java

Codes With Java — Basics Codes With Java Java tutorials & fundamentals About Contact Privacy Basic Fundamentals Java source file structure Import Statement Static Import Packages Data Type Variables Final Variable Declaration and Access Modifier Inner classes applicable modifiers Static Modifier Synchronized Native Transient Volatile Interface Introduction Interface Declaration and Implementation Interface methods and variables Naming Conflicts Interface Marker interface and Ad...
Read more

Short Circuite Operators part 4

                                                             Short Circuit Operators In  Java logical operators , if the evaluation of a logical expression exits in between before complete evaluation, then it is known as  Short-circuit . A short circuit happens because the result is clear even before the complete evaluation of the expression, and the result is returned. Short circuit evaluation avoids unnecessary work and leads to efficient processing. 1-: AND(&&) 2-:OR(||) these are exactly same as bitwise operators (&,|) except the following differences. Single Short Circuit Operator(&,|) Both arguments Should be evaluated always. relatively performance is low. Applicable for both boolean and Integral types. Double Short Circuit Operator(...
Read more

Final Variable

Final Instance Variable If the value of a variable changes from object to object, such a variable is called an instance variable . For every object, a separate copy of the instance variable will be created. Instance variables do not require explicit initialization; JVM always provides default values. Example: class Test { int x; // instance variable public static void main(String... args) { Test t = new Test(); System.out.println(t.x); // output: 0 } } If the instance variable is declared as final , then explicit initialization is mandatory. JVM will NOT provide default values. Example: class Test { final int x; } Compile-time Error: variable x might not have been initialized. Rule: A final instance variable must be initialized before constructor completion . Possible places for initialization: 1. At the time of declaration class Test { final int x = 10; } 2. Inside an instance blo...
Read more