- This topic has 1 reply, 2 voices, and was last updated 16 years, 6 months ago by
.
- Posts
Detail About Recursion and its Type
Here I am going to give a detail about Recursion in C++.
Definition: Recursion is the process where a function is called itself but stack frame will be out of limit because function call will be infinite times. So a termination condition is mandatory to a recursion.
In C++, Recursion can be divided into two types:- Run- Time Recursion: Normal as in C
- Compile- Time Recursion: By using Template
Each of these can be also divided into following types:
- Linear Recursion
- Binary Recursion
- Tail Recursion
- Mutual Recursion
- Nested Recursion
1. Linear Recursion: This recursion is the most commonly used. In this recursion a function call itself in a simple manner and by termination condition it terminates. This process called ‘Winding’ and when it returns to caller that is called ‘Un-Winding’. Termination condition also known as Base condition.
Example: Factorial calculation by linear recursion
Run-Time Version12345678910111213<br />int Fact(long n)<br />{<br />if(0>n)<br />return -1;<br />if(0 == n)<br />return 1;<br />else<br />{<br />return ( n* Fact(n-1));<br />}<br />}<br />Winding Process:
Function
called
Function returnFact(6) 6*Fact(5)
Fact(5) 5*Fact(4)
Fact(4) 4*Fact(3)
Fact(3) 3* Fact(2)
Fact(2) 2* Fact(1)
Fact(1) 1* Fact(0)Terminating Point
Fact(0) 1Unwinding Process
Fact(1) 1*1
Fact(2) 2*1
Fact(3) 3*2*1
Fact(4) 4*3*2*1
Fact(5) 5*4*3*2*1
Fact(6) 6*5*4*3*2*1Compile-Time Version
1234567891011121314151617181920<br />// template for Base Condition<br />template <><br />struct Fact<0><br />{<br />enum<br />{<br />factVal = 1<br />};<br />};<br /><br />template <int n><br />struct Fact<br />{<br />// Recursion call by linear method<br />enum<br />{<br />value = n * Fact<n - 1>::factVal<br />};<br />}; </n></int>To test it how it’s working at compile time, just call
1cout << Fact<-1>::factVal ;And compile it then compiler error will come, because no template for -1.
2. Binary Recursion: Binary Recursion is a process where function is called twice at a time inplace of once at a time. Mostly it’s using in data structure like operations for tree as traversal, finding height, merging, etc.
Example: Fibonacci number
Run Time Version Code:
123456789101112131415<br />int FibNum(int n)<br />{<br />// Base conditions<br />if (n < 1)<br />return -1;<br />if (1 == n || 2 == n)<br />return 1;<br /><br />// Recursive call by Binary Method<br />return FibNum(n - 1) + FibNum(n -<br />2); // At a time two recursive function called<br />so<br />// binary<br />}Compile Time Version Code
12345678910111213141516171819<br />// Base Conditions<br />template<><br />struct FibNum<2><br />{<br />enum { val = 1 };<br />};<br />template <><br />struct FibNum<1><br />{<br />enum { val = 1 };<br />};<br /><br />// Recursive call by Binary Method<br />template <int n><br />struct FibNum<br />{<br />enum { val= FibNum<n - 1>::val + FibNum</n><n - 2>::val };<br />};</n></int>3. Tail Recursion: In this method, recursive function is called at the last. So it’s more efficient than linear recursion method. Means you can say termination point will come(100%) only you have to put that condition.
Example: Fibonacci number
Run Time Version Code:
12345678910111213<br />int FibNum(int n, int x, int y)<br />{<br />if (1 == n) // Base Condition<br />{<br />return y;<br />}<br />else // Recursive call by Tail method<br />{<br />return FibNum(n-1, y, x+y);<br />}<br />}<br />Compile Time Version Code
1234567891011121314151617181920<br />template <int n, int x, int y><br />struct FibNum<br />{<br />// Recursive call By tail method<br />enum<br />{<br />val = FibNum<n-1, y, (x+y)>::val<br />};<br />};<br /><br />// Base Condition or Termination<br />template</int><int x, int y><br />struct FibNum<1, x, y><br />{<br />enum<br />{<br />val = y<br />};<br />};</int>4. Mutual Recursion: Functions calling each other. Let’s say FunA calling FunB and FunB calling FunA recursively. This is not actually not recursive but it’s doing same as recursive. So you can say Programming languages which are not supporting recursive calls, mutual recursion can be applied there to fulfill the requirement of recursion. Base condition can be applied to any into one or more than one or all functions.
Example: To find Even Or Odd number
Run Time Version Code:
123456789101112131415161718192021<br />bool IsOddNumber(int n)<br />{<br />// Base or Termination Condition<br />if (0 == n)<br />return 0;<br />else<br />// Recursive call by Mutual Method<br />return IsEvenNumber(n - 1);<br />}<br /><br />bool IsEvenNumber(int n)<br />{<br />// Base or Termination Condition<br />if (0 == n)<br />return 1;<br />else<br />// Recursive call by Mutual Method<br />return IsOddNumber(n - 1);<br />}<br />Compile Time Version Code
1234567891011121314151617181920212223242526272829303132333435363738394041<br />// Base Or Termination Conditions<br />template <><br />struct IsOddNumber<0><br />{<br />enum<br />{<br />val = 0<br />};<br />};<br />template <><br />struct IsEvenNumber<0><br />{<br />enum<br />{<br />val = 1<br />};<br />};<br /><br />// Recursive calls by Mutual Method<br /><br />template <int n><br />struct IsOddNumber<br />{<br />enum<br />{<br />val = n == 0 ? 0 : IsEvenNumber<n - 1>::val<br />};<br />};<br /><br /><br />template <int n><br />struct IsEvenNumber<br />{<br />enum<br />{<br />val = n == 0 ? 1 : IsOddNumber<n - 1>::val<br />};<br />};<br /><br /></n></int></n></int>3. Nested Recursion: It’s very different than all recursions. All recursion can be converted to iterative (loop) except nested recursion. You can understand this recursion by example of Ackermann function.
Example: Ackermann function
Run Time Version Code:
123456789101112131415161718192021222324<br />int Ackermann(int x, int y)<br />{<br />// Base or Termination Condition<br />if (0 == x)<br />{<br />return y + 1;<br />}<br />// Error Handling condition<br />if (x < 0 || y < 0)<br />{<br />return -1;<br />}<br />// Recursive call by Linear method<br />else if (x > 0 && 0 == y)<br />{<br />return Ackermann(x-1, 1);<br />}<br />// Recursive call by Nested method<br />else<br />{<br />return Ackermann(x-1, Ackermann(x, y-1));<br />}<br />}Compile Time Version Code
123456789101112131415161718192021222324252627<br />// Base Or Termination condition<br />template <int y><br />struct Ackermann<0, y><br />{<br />enum { val = y + 1 };<br />};<br /><br />// Recursive Call by Linear Method<br />template </int><int x><br />struct Ackermann<x, 0><br />{<br />enum<br />{<br />val = Ackermann<x-1, 1>::val<br />};<br />};<br /><br />// Recursive Call by Nested Method<br />template </int><int x, int y><br />struct Ackermann<br />{<br />Enum<br />{<br />val = Ackermann<x-1, Ackermann<x, y-1> ::val>::val<br />};<br />};</int>
- The forum ‘C Programming’ is closed to new topics and replies.