Skip to content

Instantly share code, notes, and snippets.

@yusuketanabe
Created February 2, 2022 03:23
Show Gist options
  • Save yusuketanabe/677c073eedf037607e2c77d81f0cf694 to your computer and use it in GitHub Desktop.
Save yusuketanabe/677c073eedf037607e2c77d81f0cf694 to your computer and use it in GitHub Desktop.
Recursive function memo
#include <iostream>
#include <vector>
// Sum of array elements
// sum of [i, i+1] = [i] + [i+1]
int array_sum_from_i(std::vector<int> &data, int i) {
// Base
if (i == data.size()) return 0;
// Recursive
int s = array_sum_from_i(data, i+1);
return data[i] + s;
}
int array_sum(std::vector<int> &data) {
return array_sum_from_i(data, 0);
}
int main() {
std::vector<int> a = {0,1,2,3};
std::cout << array_sum(a) << std::endl;
std::vector<int> b = {};
std::cout << array_sum(b) << std::endl;
std::vector<int> c = {5,5,5,5,5};
std::cout << array_sum(c) << std::endl;
}
/* output
6
0
25
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment