You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: contrib/ds-algorithms/recursion.md
+9-32
Original file line number
Diff line number
Diff line change
@@ -2,7 +2,7 @@
2
2
3
3
When a function calls itself to solve smaller instances of the same problem until a specified condition is fulfilled is called recursion. It is used for tasks that can be divided into smaller sub-tasks.
4
4
5
-
# How Recursion Works
5
+
##How Recursion Works
6
6
7
7
To solve a problem using recursion we must define:
8
8
- Base condition :- The condition under which recursion ends.
@@ -17,7 +17,7 @@ When a recursive function is called, the following sequence of events occurs:
17
17
- Stack Management: Each recursive call is placed on the call stack. The stack keeps track of each function call, its argument, and the point to return to once the call completes.
18
18
- Unwinding the Stack: When the base case is eventually met, the function returns a value, and the stack starts unwinding, returning values to previous function calls until the initial call is resolved.
19
19
20
-
# Python Code: Factorial using Recursion
20
+
##Python Code: Factorial using Recursion
21
21
22
22
```python
23
23
deffact(n):
@@ -30,7 +30,7 @@ if __name__ == "__main__":
30
30
print("Factorial of", n, "is", fact(n))
31
31
```
32
32
33
-
## Explanation
33
+
###Explanation
34
34
35
35
This Python script calculates the factorial of a given number using recursion.
36
36
@@ -43,8 +43,7 @@ This Python script calculates the factorial of a given number using recursion.
43
43
- The main section prompts the user to enter a positive number.
44
44
- It then calls the `fact` function with the input number and prints the result.
45
45
46
-
### Example : Let n = 4
47
-
46
+
#### Example : Let n = 4
48
47
49
48
The recursion unfolds as follows:
50
49
1. When `fact(4)` is called, it computes `4 * fact(3)`.
@@ -55,48 +54,26 @@ The recursion unfolds as follows:
55
54
6.`fact(4)` receives the value from `fact(3)`, resulting in `4 * 6` i.e. `24`.
56
55
7. Finally, `fact(4)` returns 24 to the main function.
57
56
58
-
59
57
#### So, the result is 24.
60
58
61
-
62
-
63
-
# What is Stack Overflow in Recursion
59
+
#### What is Stack Overflow in Recursion?
64
60
65
61
Stack overflow is an error that occurs when the call stack memory limit is exceeded. During execution of recursion calls they are simultaneously stored in a recursion stack waiting for the recursive function to be completed. Without a base case, the function would call itself indefinitely, leading to a stack overflow.
66
62
67
-
# Example
68
-
69
-
- Factorial of a Number
70
-
71
-
The factorial of i natural numbers is nth integer multiplied by factorial of (i-1) numbers. The base case is if i=0 we return 1 as factorial of 0 is 1.
72
-
73
-
```python
74
-
deffactorial(i):
75
-
#base case
76
-
if i==0 :
77
-
return1
78
-
#recursive case
79
-
else :
80
-
return i * factorial(i-1)
81
-
i =6
82
-
print("Factorial of i is :", factorial(i)) # Output- Factorial of i is :720
83
-
```
84
-
# What is Backtracking
63
+
## What is Backtracking
85
64
86
65
Backtracking is a recursive algorithmic technique used to solve problems by exploring all possible solutions and discarding those that do not meet the problem's constraints. It is particularly useful for problems involving combinations, permutations, and finding paths in a grid.
87
66
88
-
# How Backtracking Works
67
+
##How Backtracking Works
89
68
90
69
- Incremental Solution Building: Solutions are built one step at a time.
91
70
- Feasibility Check: At each step, a check is made to see if the current partial solution is valid.
92
71
- Backtracking: If a partial solution is found to be invalid, the algorithm backtracks by removing the last added part of the solution and trying the next possibility.
93
72
- Exploration of All Possibilities: The process continues recursively, exploring all possible paths, until a solution is found or all possibilities are exhausted.
94
73
95
-
# Example
96
-
97
-
- Word Search
74
+
## Example: Word Search
98
75
99
-
Given a 2D grid of characters and a word, determine if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
76
+
Given a 2D grid of characters and a word, determine if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
100
77
101
78
Algorithm for Solving the Word Search Problem with Backtracking:
102
79
- Start at each cell: Attempt to find the word starting from each cell.
0 commit comments