Recursion - HackMD

# Recursion It is a process in which a function calls itself directly or indirectly and the corresponding function is called recursive function. There must be some base condition for recursion to terminate upon, otherwise the function will go in an infinite loop. ## Examples ### Example 1 ```c void func1(int n) { if (n > 0) { printf("%d ", n); func1(n-1); } } int main() { int x = 3; func1(3); return 0; } ``` #### Tracing ```graphviz graph G { node [color = white] edge[color = "#8e1d1d"] "fun1(3)" -- {3, "fun1(2)"} "fun1(2)" -- {2, "fun1(1)"} "fun1(1)" -- {1, "fun1(0)"} "fun1(0)" -- X } ``` **Result: 3 2 1** ### Example 2 ```c void fun2(int n) { if (n > 0) { fun(n-1); printf("%d ", n); } } int main() { int x = 3; fun2(3); return 0; } ``` #### Tracing ```graphviz graph G { node [shape = box, color = white] edge[color = "#8e1d1d"] "fun2(3)" -- {"fun2(2)", 3} "fun2(2)" -- {"fun2(1)", 2} "fun2(1)" -- {"fun2(0)", 1} "fun2(0)" -- X } ``` **Result: 1 2 3** ### Difference between above examples Difference between `fun1()` and `fun2()` was that `fun1()` was printing the result and then recursively calling the function, while `fun2()` first called the function and then after termination of last call printed the result. Basically `fun1()` printed reverse output of `fun2()`. ## General form of a recursive function ```c Type function(parameter) { if (<base condition>) { statements -> Execute at calling phase function(parameter) statements -> Execute at returning phase } } ``` ## Static Variables in Recursion Static variables are variables which are initiliazed only when the program is loaded in the main memory(RAM). ### Example ```c int fun(int n) { static int x = 0; if (n > 0) { x++; return fun(n-1) + x; } return 0; } int main() { int a = 5; printf("%d", fun(a)); return 0; } ``` #### Tracing ```graphviz digraph G { node [shape=box, color=white] edge[color = "#8e1d1d"] subgraph G1 { edge[dir=none] "fun(5)" -> "fun(4) + 5" "fun(4) + 5" -> "fun(3) + 5" "fun(3) + 5" -> "fun(2) + 5" "fun(2) + 5" -> "fun(1) + 5" "fun(1) + 5" -> "fun(0) + 5" "fun(0) + 5" -> "" [color = white] } subgraph G2 { edge[dir=back, color = black] "fun(5)" -> "= 25" "fun(4) + 5" -> "= 20" "fun(3) + 5" -> "= 15" "fun(2) + 5" -> "= 10" "fun(1) + 5" -> "= 5" "fun(0) + 5" -> "= 0" } } ``` Here the value of x is calculated at the last fun(0) call and then returned to the the previous calls. **Result: 25** # Types of Recursion **1. Tail Recursion 2. Head Recursion 3. Tree Recursion 4. Indirect Recursion 5. Nested Recursion** ## 1. Tail Recursion If a recursive function has a recursive call as the last statement in the function, then it is called Tail recursion. ```c Type function(n) { if (<base condition>) { statement statement function(n-1) } } ``` Tail recursion can be **easily** converted to a loop (while, for) and the loop will have less space complexity than Tail recusion. ### Analysis | Method | Time | Space | | -------------- | ---- | ----- | | Tail Recursion | O(n) | O(n) | | Loops | O(n) | O(1) | Therefore, it is recommended to convert a Tail recursion to a loop as it is more efficient in terms of space complexity. ## 2. Head Recursion If a recursive function hsd the recursive call as the first statement(after base condition), then it is called Head recursion. All the processing is done after the function call termination. Head recursion can be converted to loops but it **isn't as easy** as Tail recursion's conversion. ```c Type function(n) { if (<base condition>) { function(n-1) statement statement } } ``` ### Analysis | Method | Time | Space | | -------------- | ---- | ----- | | Tail Recursion | O(n) | O(n) | | Loops | O(n) | O(1) | ## 3. Tree Recursion If a recursive function is calling itself multiple times then it is known as Tree recursion. ### Example ```c void fun(int n) { i (n > 0) { printf("%d ", n); fun(n-1); fun(n-1); } } ``` #### Tracing ```graphviz graph G { node [shape=box, color=white] edge[color = "#8e1d1d"] // level 0 "fun(3)" -- {0, node1, node2} // level 1 node1 -- {"21", node3, node4} node2 -- {"22", node7, node8} // level 2 node3 -- {"11", node5, node6} node4 -- {"12", node9, node10} node7 -- {"13", node11, node12} node8 -- {"14", node13, node14} // level 3 node5 -- X1 node6 -- X2 node9 -- X3 node10 -- X4 node11 -- X5 node12 -- X6 node13 -- X7 node14 -- X8 node1 [label="fun(2)"] node2 [label="fun(2)"] node3 [label="fun(1)"] node4 [label="fun(1)"] node5 [label="fun(0)"] node6 [label="fun(0)"] node7 [label="fun(1)"] node8 [label="fun(1)"] node9 [label="fun(0)"] node10 [label="fun(0)"] node11 [label="fun(0)"] node12 [label="fun(0)"] node13 [label="fun(0)"] node14 [label="fun(0)"] X1[label="X"] X2[label="X"] X3[label="X"] X4[label="X"] X5[label="X"] X6[label="X"] X7[label="X"] X8[label="X"] "11"[label="1"] "12"[label="1"] "13"[label="1"] "14"[label="1"] "21"[label="2"] "22"[label="2"] } ``` **Result: 3 2 1 1 2 1 1** ### Analysis **Time  - O(2n) Space - O(n)** ## 4. Indirect Recursion In Indirect recusion there maybe more than 1 function and they maybe calling each other in a circular fashion. ### Example ```c void funA(int n) { if (n > 0) { printf("%d ", n); funB(n-1); } } void funB(int n) { if (n > 1) { printf("%d ", n); funA(n/2); } } ``` #### Tracing ```graphviz graph G { node [shape = box, color = white] edge[color = "#8e1d1d"] "funA(20)" -- {20 "funB(19)"} "funB(19)" -- {19 "funA(9)"} "funA(9)" -- {9 "funB(8)"} "funB(8)" -- {8 "funA(4)"} "funA(4)" -- {4 "funB(3)"} "funB(3)" -- {3 "funA(1)"} "funA(1)" -- {1 "funB(0)"} "funB(0)" -- {"X"} } ``` **Result: 20 19 9 8 4 3 1** ## 5. Nested Recursion In Nested recursion, recursive function will pass the parameter as a recursive call itself. Basically calling the function on the return value of parameter function. ### Example ```c int fun(int n) { if (n > 100) { return n - 10; } return fun(fun(n + 11)); } ``` #### Tracing ```graphviz digraph G { node [shape = box, color = white] edge[color = "#8e1d1d"] subgraph G1 { edge [dir = back, color = black] "fun(fun(95+11))" -> "fun(fun(106))" [label = " 96"] "fun(fun(96+11))" -> "fun(fun(107))" [label = " 97"] "fun(fun(97+11))" -> "fun(fun(108))" [label = " 98"] "fun(fun(98+11))" -> "fun(fun(109))" [label = " 99"] "fun(fun(99+11))" -> "fun(fun(110))" [label = " 100"] "fun(fun(100+11))" -> "fun(fun(101))" [label = " 101"] } subgraph G2 { edge [dir = none] "fun(95)" -> "fun(fun(95+11))" "fun(fun(95+11))" -> "fun(96)" "fun(96)" -> "fun(fun(96+11))" "fun(fun(96+11))" -> "fun(97)" "fun(97)" -> "fun(fun(97+11))" "fun(fun(97+11))" -> "fun(98)" "fun(98)" -> "fun(fun(98+11))" "fun(fun(98+11))" -> "fun(99)" "fun(99)" -> "fun(fun(99+11))" "fun(fun(99+11))" -> "fun(100)" "fun(100)" -> "fun(fun(100+11))" "fun(fun(100+11))" -> "fun(101)" "fun(101)" -> "91" } subgraph G3 { edge [dir = none, color = black] "fun(fun(106))" -> 96 "fun(fun(107))" -> 97 "fun(fun(108))" -> 98 "fun(fun(109))" -> 99 "fun(fun(110))" -> 100 "fun(fun(101))" -> 101 } } ``` **Result: 91** # Problem Solving using Recursion ## 1. Sum of first 'n' natural numbers: ### Definition: $$ \begin{aligned} & Sum(n) = 1 + 2 + 3 + ... + (n-1) + n \\ & Sum(n) = Sum(n-1) + n \end{aligned} $$ ### Recurrance relation: $$ Sum(n) = \begin{cases} 0 & \text{$n$ = 0} \\[2ex] Sum(n-1) + n & \text{$n$ > 0} \end{cases} $$ ### Implementation ```c int sum(int n) { if (n == 0) return 0; else return sum(n-1) + n; } ``` ### Tracing ```graphviz digraph G { node [shape = box, color = white] edge[color = "#8e1d1d"] subgraph G1 { edge [dir = none] "sum(5)" -> "sum(4) + 5" "sum(4) + 5" -> "sum(3) + 4" "sum(3) + 4" -> "sum(2) + 3" "sum(2) + 3" -> "sum(1) + 2" "sum(1) + 2" -> "sum(0) + 1" "sum(0) + 1" -> "" [color = white] } subgraph G2 { edge[dir=back, color = black] "sum(5)" -> "= 15" "sum(4) + 5" -> "= 10" "sum(3) + 4" -> "= 6" "sum(2) + 3" -> "= 3" "sum(1) + 2" -> "= 1" "sum(0) + 1" -> "= 0" } } ``` **Result = 15** ### Analysis **Time - O(n) Space - O(n)** ## 2. Factorial of a number: ### Definition: $$ \begin{aligned} & n! = 1 * 2 * 3 * ... * n \\ \\ & Fact(n) = 1 * 2 * 3 * ... * (n-1) * n\\ & Fact(n) = Fact(n-1) * n \end{aligned} $$ ### Recurrance relation: $$ Fact(n) = \begin{cases} 1 & \text{$n$ = 0} \\[2ex] Fact(n-1) * n & \text{$n$ > 0} \end{cases} $$ ### Implementation ```c int fact(int n) { if (n == 0) return 1; else fact(n-1) * n; } ``` ### Tracing ```graphviz digraph G { node [shape = box, color = white] edge[color = "#8e1d1d"] subgraph G1 { edge [dir = none] "fact(5)" -> "fact(4) * 5" "fact(4) * 5" -> "fact(3) * 4" "fact(3) * 4" -> "fact(2) * 3" "fact(2) * 3" -> "fact(1) * 2" "fact(1) * 2" -> "fact(0) * 1" "fact(0) * 1" -> "" [color = white] } subgraph G2 { edge[dir=back, color = black] "fact(5)" -> "= 120" "fact(4) * 5" -> "= 24" "fact(3) * 4" -> "= 6" "fact(2) * 3" -> "= 2" "fact(1) * 2" -> "1" "fact(0) * 1" -> "11" } "11"[label = "= 1"] } ``` ## 3. Exponentiation(mn) ### Definition: $$ \begin{aligned} & m^n = m * m * m * ... \text{ for $n$ times} \\ \\ & Pow(m, n) = m * m * m * ... * n-1 \text{ times}*m\\ & Pow(m, n) = Pow(m, n-1) * m \end{aligned} $$ ### Recurrance relation: $$ Pow(m, n) = \begin{cases} 1 & \text{$n$ = 0} \\[2ex] Pow(m, n-1) * m & \text{$n$ > 0} \end{cases} $$ ### Implementation ```c int pow(int m, int n) { if (n == 0) return 1; else return pow(m, n-1) * m; } ``` ### Tracing ```graphviz digraph G { node [shape = box, color = white] edge[color = "#8e1d1d"] subgraph G1 { edge [dir = none] "pow(2,6)" -> "pow(2,5) * 2" "pow(2,5) * 2" -> "pow(2,4) * 2" "pow(2,4) * 2" -> "pow(2,3) * 2" "pow(2,3) * 2" -> "pow(2,2) * 2" "pow(2,2) * 2" -> "pow(2,1) * 2" "pow(2,1) * 2" -> "pow(2,0) * 2" "pow(2,0) * 2" -> "" [color = white] } subgraph G2 { edge[dir=back, color = black] "pow(2,6)" -> "= 64" "pow(2,5) * 2" -> "= 32" "pow(2,4) * 2" -> "= 16" "pow(2,3) * 2" -> "= 8" "pow(2,2) * 2" -> "= 4" "pow(2,1) * 2" -> "= 2" "pow(2,0) * 2" -> "= 1" } } ``` ### Optimization: When n is a even number we can reduce the _no. of multiplication_ by adding another if statement and check for even exponent and then just perform `pow(m*m, (n-1)/2)`. And in case of odd exponent we can perform `m * pow(m, n-1)`. For example, in case of even number, $$ \begin{aligned} 2^8 & = (2^2)^4 \\ & = (2*2)^4 \end{aligned} $$ and for odd number, $$ \begin{aligned} 2^9 & = 2 * (2^2)^4 \\ & = 2 * (2*2)^4 \end{aligned} $$ ### Implementation ```c int pow(int m, int n) { if (n == 0) return 1; else if (n % 2 == 0) return pow(m * m, (n-1)/2); else return pow(m, n-1) * m; } ``` ### Tracing ```graphviz digraph G { node [shape = box, color = white] edge[color = "#8e1d1d"] subgraph G1 { edge [dir = none] "pow(2,6)" -> "pow(2*2,3) * 2" "pow(2*2,3) * 2" -> "pow(2*2*2*2,1) * 2^2" "pow(2*2*2*2,1) * 2^2" -> "pow(2*2*2*2*2*2*2*2,0) * 2^4" "pow(2*2*2*2*2*2*2*2,0) * 2^4" -> "" [color = white] } subgraph G2 { edge[dir=back, color = black] "pow(2,6)" -> "2^6" "pow(2*2,3) * 2" -> "261" "pow(2*2*2*2,1) * 2^2" -> "2^4" "pow(2*2*2*2*2*2*2*2,0) * 2^4" -> "1" } "261"[label = "2^6"] } ``` ## 4. Taylor series expansion for ex ### Definition: $$ e^x = 1 + \frac{x}{1} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + ... \frac{x^n}{n!} $$ ### Implementation ```c double e(int x, int n) { static double p = 1, f = 1; if (n == 0) return 1; else { double r = e(x, n-1); p *= x; f *= n; return r + p/f; } } ``` ### Tracing ```graphviz digraph G { node [shape = box, color = white] edge[color = "#8e1d1d"] subgraph G1 { edge [dir = none] "e(x,4)" -> "e(x,3)" "e(x,3)" -> "e(x,2)" "e(x,2)" -> "e(x,1)" "e(x,1)" -> "e(x,0)" } subgraph G2 { edge[dir=back, color = black] "e(x,4)" -> "= 1 + x + x^2/2! + x^3/3! + x^4/4!" "e(x,3)" -> "= 1 + x + x^2/2! + x^3/3!" "e(x,2)" -> "= 1 + x + x^2/2!" "e(x,1)" -> "p = p * x, f = f * 1" "e(x,1)" -> "1 + p/f" "e(x,0)" -> "1" } } ``` ## Optimization of Taylors series using Harner's Rule ### Definition: $$ \begin{aligned} e^x & = 1 + \frac{x}{1} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + ... \frac{x^n}{n!} \\ & = 1 + \frac{x}{1} \left[1+\frac{x}{2} + \frac{x^2}{2*3} + \frac{x^3}{2*3*4} \right] \\ & = 1 + \frac{x}{1} \left[1 + \frac{x}{2} \left[1 + \frac{x}{3} + \frac{x^2}{3*4} \right]\right] \\ & = 1 + \frac{x}{1} \left[1+\frac{x}{2} \left[1+\frac{x}{3} \left[1 + \frac{x}{4} \right]\right]\right] \end{aligned} $$ This optimization reduced the **Time** complexity from **O(n2) to O(n)**. ### Implementation ```c int e(int x, int n) { static int s = 1; if (n == 0) return s; else { s = 1 + x/n * s; return e(x, n-1); } } ``` ## 5. Fibonacci Series ### Definition: $Fib(n) = \text{0 1 1 2 3 5 8 13 21 }...$ ### Recurrance relation: $$ Fib(n) = \begin{cases} 0 & \text{$n$ = 0} \\[2ex] 1 & \text{$n$ = 1} \\[2ex] Fib(n-2) + Fib(n-1) & \text{$n$ > 1} \end{cases} $$ ### Implementation ```c int fib(int n) { if (n <= 1) return n; else return fib(n-2) + fib(n-1); } ``` ### Tracing ![](https://i.imgur.com/kqQDDGy.png) ### Analysis **Time  - O(2n) Space - O(1)** ## Optimization of Fibonacci series using Memoization **Memoization** is a technique by which we store the results of function call so that they shall be utilized in future if there is same call. This method helps reduce excessive function calls. ### Implementation ```c int F[100]; int fib(int n) { if (n <= 1) { F[n] = n; return n; } else { if (F[n-2] == -1) F[n-2] = fib(n-2); if (F[n-1] == -1) F[n-1] = fib(n-1); F[n] = F[n-2] + F[n-1]; return F[n] } } ``` ### Analysis **Time  - O(n) Space - O(1)** ## 6. Combinations ### Defintion: $$ _n\mathrm{ C }_r = \frac{n!}{r!(n-r)!} $$ ### Implementaion using Factoial() ```c int C(int n, int r) { int t1 = fact(n); int t2 = fact(r); int t3 = fact(n-r); return t1 / (t2 * t3); } ``` ### Pascals Triangle ![](https://i.imgur.com/Ztyk8B4.png) ### Implementation using Recursion ```c int c(int n, int r) { if (r == 0 || n == r) return 1; else return C(n-1, r-1)+ C(n-1, r); } ``` ## Towers Of Hanoi ![](https://i.imgur.com/bENbj7s.png) ``` TOH(1, A, B, C) Move Disk from A to C using B TOH(2, A, B, C) 1. TOH(1, A, C, B) 2. TOH(1, A, B, C) 3. TOH(1, B, A, C) TOH(n, A, B, C) 1. TOH(n-1, A, C, B) 2. TOH(1, A, B, C) 3. TOH(n-1, B, A, C) ``` ### Implementation ```c void TOH(int n, int A, int B, int C) { if (n > 0) { TOH(n-1, A, C, B); printf("from %d to %d", A, C); TOH(n-1, B, A, C); } } ``` ### Tracing ```graphviz digraph G { node [shape = rect] edge [color = "#8e1d1d"] subgraph G1 { edge [dir = none] "3,1,2,3" -> "2,1,3,2" "3,1,2,3" -> "131" [color = black] "3,1,2,3" -> "2,2,1,3" "2,1,3,2" -> "1,1,2,31" "2,1,3,2" -> "12" [color = black] "2,1,3,2" -> "1,3,1,2" "1,1,2,31" -> "0,1,3,2" "1,1,2,31" -> "132" [color = black] "1,1,2,31" -> "01" "0,1,3,2" -> "X" "1,3,1,2" -> "02" "1,3,1,2" -> "32" [color = black] "1,3,1,2" -> "03" "2,2,1,3" -> "1,2,3,1" "2,2,1,3" -> "23" [color = black] "2,2,1,3" -> "1,1,2,32" "1,2,3,1" -> "04" "1,2,3,1" -> "21" [color = black] "1,2,3,1" -> "05" "1,1,2,32" -> "06" "1,1,2,32" -> "133" [color = black] "1,1,2,32" -> "07" } "01" [label = "0,___"] "02" [label = "0,___"] "03" [label = "0,___"] "04" [label = "0,___"] "05" [label = "0,___"] "06" [label = "0,___"] "07" [label = "0,___"] "12" [color = white, label = "1 to 2"] "131" [color = white, label = "1 to 3"] "132" [color = white, label = "1 to 3"] "133" [color = white, label = "1 to 3"] "32" [color = white, label = "3 to 2"] "21" [color = white, label = "2 to 1"] "23" [color = white, label = "2 to 3"] "1,1,2,31" [label = "1,1,2,3"] "1,1,2,32" [label = "1,1,2,3"] } ``` ### Analysis **Time  - O(2n) Space - O(n)**

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.