-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathrecursionOne.java
More file actions
107 lines (71 loc) · 3.34 KB
/
Copy pathrecursionOne.java
File metadata and controls
107 lines (71 loc) · 3.34 KB
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
public class recursionOne {
// Given n of 1 or more, return the factorial of n, which is n * (n-1) * (n-2) ... 1. Compute the result recursively (without loops).
// factorial(1) → 1
// factorial(2) → 2
// factorial(3) → 6
public int factorial(int n) {
if (n == 1) {
return 1;
}
return n * factorial(n - 1);
}
// We have a number of bunnies and each bunny has two big floppy ears. We want to compute the total number of ears across all the bunnies recursively (without loops or multiplication).
// bunnyEars(0) → 0
// bunnyEars(1) → 2
// bunnyEars(2) → 4
public int bunnyEars(int bunnies) {
if (bunnies == 0) {
return 0;
}
return 2 + bunnyEars(bunnies - 1);
}
// The fibonacci sequence is a famous bit of mathematics, and it happens to have a recursive definition. The first two values in the sequence are 0 and 1 (essentially 2 base cases). Each subsequent value is the sum of the previous two values, so the whole sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21 and so on. Define a recursive fibonacci(n) method that returns the nth fibonacci number, with n=0 representing the start of the sequence.
// fibonacci(0) → 0
// fibonacci(1) → 1
// fibonacci(2) → 1
public int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 2) + fibonacci(n - 1);
}
// We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3, ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3 ears, because they each have a raised foot. Recursively return the number of "ears" in the bunny line 1, 2, ... n (without loops or multiplication).
// bunnyEars2(0) → 0
// bunnyEars2(1) → 2
// bunnyEars2(2) → 5
public int bunnyEars2(int bunnies) {
if (bunnies == 0) {
return 0;
}
if (bunnies % 2 != 0) {
return 2 + bunnyEars2(bunnies - 1);
}
return 3 + bunnyEars2(bunnies - 1);
}
// We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on. Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows.
// triangle(0) → 0
// triangle(1) → 1
// triangle(2) → 3
public int triangle(int rows) {
if (rows == 0) {
return 0;
}
return rows + triangle(rows - 1);
}
// Given a non-negative int n, return the sum of its digits recursively (no loops). Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).
// sumDigits(126) → 9
// sumDigits(49) → 13
// sumDigits(12) → 3
public int sumDigits(int n) {
if (n == 0) {
return 0;
}
return n % 10 + sumDigits(n / 10);
}
// Given a non-negative int n, return the count of the occurrences of 7 as a digit, so for example 717 yields 2. (no loops). Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).
// count7(717) → 2
// count7(7) → 1
// count7(123) → 0
public int count7(int n) {
}
}