1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
[\<- Notes 02/12](02-12.md)
---
# Arguments for main()
To add arguments to main, do something like this:
```
int main(int argc, char *argv[])
```
- `int argc` is the number of arguments
- the name (`a.out`) is an argument, so there will always be at least one argument
- `char *argv[]` is an array of strings, where each is an argument for the program
- example, if you want two arguments, check that argc is the correct value: `argc == 3` (since you need one for the execution)
# Recursion (not on Midterm #2)
- A recursive function calls itself or is part of a cycle in the sequence of function calls
- Allows for the possibility for a function call to be repeated with different parameters
- Alternative to iteration
- less efficient
- more simple
- You will never use a loop ina recursive function
- recursion is meant to substitute the use of loops
- Problems that lend themselves to a Recursive Solution:
- simple cases with a a straightforward solution
- cases can be redefined to be simplified
- redefinition process can reduce complex problems to simple cases (relatively easy to solve)
General form:
```
if this is a **simple case**
solve it
else
**redefine** the problem using recursion
```
Example: we want to multiply 6 by 3, but we only know how to add, and that x \* 1 = x
```
int multiply(int m, int n){
int ans;
if(n == 1) ans = m;
else ans = m + multiply(m, n-1);
return(ans);
}
```
- Recursion can be useful for processing varying-length lists
- Strings
- Linked-lists
- Etc.
Example: write a function to count the number of times a particular character appears in a string
```
int count(char ch, char *str){
if(*str == '\0') return 0;
if(ch == *str) return(1 + count(ch, str+1));
else return(count(ch, str+1));
}
```
## Traversing Recursive Functions
- *Hand Tracing* can be used to better understand how recursion works
- going through function calls step-by-step
- Parameters and Local Variable Stacks
- Local function values are kept in a *stack*
- A *stack* is a data structure
- last data item in is first data item out
- *system stack* is an area in memory where parameters and local variables are
- allocated when a function is called
- deallocated (freed) when the function returns
- When a program is executing:
- Calling a function "pushes" its local values onto the top of the stack
- Returning from a function "pops" its local values from the top of the stack
## Math Function and Recursion
- Many mathematical functions are defined recursively
- Example: Factorial
- 0! = 1
- n! = n \* (n-1)! for n>0
- As a function:
```
int factorial(int n){
int ans;
if(n == 0) ans = 1;
else ans = n * factorial(n-1);
return(ans);
}
```
- Example: The Fibonacci Sequence ([Spiral Out](https://www.youtube.com/watch?v=Y7JG63IuaWs))
```
int fibonacci(int n){
int ans;
if(n == 0 || n == 1) ans = n;
else ans = fibonacci(n-1) + fibonacci(n-2);
return ans;
}
```
---
[-> Notes 02/21](02-21.md)
|
