CS162 - 7A
TABLE OF CONTENTS
Recursion
Is another way to do the same thing again and again by self-referencing.
void A(int a, int b) {
//do something something
A(b, a);
//do something something
}
- The action of getting back to the previous function call in recursion is called backtracking.
- Using recursion can make a repetition but sometimes loops are better than recursion.
- Recursion looks simpler but hard to debug.
- All the problems solved by recursion can be solved by loops (by rebuild the stack).
Look at the code below, can you tell what it does?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void strange() {
int t;
cin >> t;
if (t!=0) {
strange();
cout << t << " ";
}
}
int main {
cout << "Pls input numbers (0 to stop)" << endl;
strange();
cout << endl;
return 0;
}
Answer: It will input a list of numbers (until 0) then print that list in reversed order.
Problem statement(s)
- Given a positive integer $N$, you are asked to implement a program to print out all permutations of $1$ to $N$.
Problem 1
Student’s code
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
#include <iostream>
using namespace std;
void Permutation(int i, int n, int* &arr, bool* &avail);
int main() {
int n;
cout << "Pls input an integer number: ";
cin >> n;
int* arr = new int[n];
bool* avail = new bool[n];
for(int i = 0; i < n; i++)
avail[i] = 1;
Permutation(0, n, arr, avail);
delete[] arr;
delete[] avail;
return 0;
}
void Permutation(int i, int n, int* &arr, bool* &avail) {
if(i==n) {
for(int j=0; j<n; j++) cout<<arr[j]<<" ";
cout<<"\n";
return;
}
for(int x=0; x<n; x++) {
if(avail[x]) {
arr[i] = x+1;
avail[x] = 0;
Permutation(i+1, n, arr, avail);
avail[x] = 1;
}
}
}