Recursion vs Iteration
🎡Recursion
: Method that solves the problem by calling the algorithms (or function) back. A suitable method for circular definition.
🔎 Recursion principle
Divide-and-conquer
Divide-and-conquer
: Divide the problem into a set of sub problems. recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
🎯 Recursion types
-
tail recursion
: easily implemented using iteration
ex) return n*factorial (n-1);
-
head recursion
: difficult to implement using iteration
ex) return factorial(n-1) * n;
-
multi recursion
: difficult to implement using iteration
ex)
function(A, n)
{
//Recursive call of 2.
function(A, n-1)
function(A, n-1)
}
⚖ Recursion VS Iteration
-
Recursion
: using recursive calls
pros - Good choice for recursive problems (easy to implement)
cons - overhead of function calls -> usually slower execution time
-
Iteration
: using 'for' or 'while' loop
pros - fast execution time
cons - programming can be often vety difficult for recursive problems
Then, what is best strategy?
-> It depends on problems.
🧬 Factorial
tail recursion
: easily implemented using iteration
ex) return n*factorial (n-1);
head recursion
: difficult to implement using iteration
ex) return factorial(n-1) * n;
multi recursion
: difficult to implement using iteration
ex)
function(A, n)
{
//Recursive call of 2.
function(A, n-1)
function(A, n-1)
}
-
Recursion
: using recursive calls
pros - Good choice for recursive problems (easy to implement)
cons - overhead of function calls -> usually slower execution time -
Iteration
: using 'for' or 'while' loop
pros - fast execution time
cons - programming can be often vety difficult for recursive problemsThen, what is best strategy?
-> It depends on problems.
🧬 Factorial
1. recursive Implimentation of Factorial
int factorial_recur(int n) {
if (n <= 1) return 1;
else return n * factorial(n - 1);
}
T(N) = T(N-1) + 1 --> Time Complexity : O(N)
2. Iterative Implimentation of Factorial
int factorial_iter(int n) {
int mul = 1;
for (int i = n; i >= 1; i--) {
mul *= n; // n* (n-1) ... 2*1 ;
}
return mul ;
}
Time Complexity : O(N)
3. compare
📌 Power Computation
: Let's find n-squared value of x :x^n
1. recursive Implimentation of Power Computation
double power_iter(double x, int n) { //x^n
int i;
double r = 1.0;
for (i = 0; i < n; i++) {
r = r * x;
}
return r;
}
Time Complexity : O(N)
2. Iterative Implimentation of Power Computation
double power_recur(double x, int n) {
if (n == 0) return 1;
else if ((n % 2) == 0)
return power(x * x, n / 2);
else
return x * power(x * x, n-1/ 2);
}
Time Complexity : T(N) = T(2/N) +C -> O(logN)
3. compare
iteration is not good choice😥
📝 Fibonacci Series
1. recursive Implimentation of Fibonacci Series
int fib_recur(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib_recur(n - 1) + fib_recur(n - 2);
}
Time Complexity : T(N) < 2^(N-1) -> O(2^N)
why ? for fib(n), maximum depth of tree is n-1.
and tree must be not filled with leaf node fully.
2. Iterative Implimentation of Fibonacci Series
: to get fib(n), calculating one by one by one from the first two terms .
int fib_iter(int n) {
int temp, current = 1, last = 0; //the first two terms of Fibonacci sequence.
if (n < 2) return n;
else {
for (int i = 1; i < n; i++) {
temp = current; //keep the last value.
current = last + current ; //Renewal Nth term
last = temp; //Save it for the next calculation.
}
}
return current;
}
Time Complexity : O(N)
3. compare
♟Hanoi tower
: move n disc stacked on rod A to rod C.
Divide and conquer
1. recursive Implimentation of Hanoi tower
void hanoi_tower(int n, char from, char tmp, char to)
{
if (n == 1) printf("Move 1 disc from % c to % c.\n", from, to);
else {
hanoi_tower(n - 1, from, to, tmp);
printf("Move disc % d from % c to % c.\n", n, from, to);
hanoi_tower(n - 1, tmp, from, to);
}
}
Time Complexity : T(N) = 2T(N-1)+1 = 2^N -1 -> O(2^N)
2. Iterative Implimentation of Hanoi tower
3. compare
🎫Binary Search
: when a array of ordered numbers is given, find an index k where ak=b.
1. recursive Implimentation of Binary Search
int search_iter(A, b)
for i=1 to n
if(A[i] == b)
k=i;
return k
Time Complexity : O(N)
2. Iterative Implimentation of Binary Search
int search_recur(A, b, start, end)
if(start>end) return -1;
int median = (start+end)/2;
if(A[median]<b)
search_recur(A, b, median, end);
else if(A[median]>b)
search_recur(A, b, start, median);
else
return median;
Time Complexity : T(N)=t(N/2)+C -> O(logN)
3. compare
📚
🧶
🎯⚒🧬⚔🕯🔎💳📂🎫♦⚖🛢
⚙📖📕📗📘✏✒🖋🖊🖌🖍📝📌🗂📎
Author And Source
이 문제에 관하여(Recursion vs Iteration), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@flowersayo/Recursion-vs-Iteration저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)