How to avoiding duplicated computing of recursive function like this one:
func(n) = func(n-1) + func(n-2) + func(n-3) and func(1) == func(2) == 1 and func(3) == 2.
or function like this: fabonaci:
fabonaci(n) = fabonaci(n-1) + fabonaci(n-2).
1 int fabo(int n, int* ptr)
2 {
3 printf("fabo(%d)\n", n);
4 if(n < 3)
5 {
6 *ptr = 1;
7 return 1;
8 }
9 else {
10 int tmp;
11 *ptr = fabo(n - 1, &tmp);
12
13 return *ptr + tmp;
14 }
15 }
16 int fabonaci(int n)
17 {
18 int tmp;
19 return fabo(n, &tmp);
20 }
21
22 int xxx(int n)
23 {
24 printf("xxx(%d)\n", n);
25 if(n < 3)return 1;
26 else return xxx(n-1)+xxx(n-2);
27 }
28 int main()
29 {
30 int n = fabonaci(10);
31 printf("n = %d\n", n);
32
33 n = xxx(10);
34 printf("n = %d\n", n);
35 getchar();
36 return 0;
37 }
1 /************************************************************************/
2 /* func(n) = func(n-1) + func(n-2) + func(n-3) */
3 /* func(1) = 1; func(2) = 1; func(3) = 2; */
4 /************************************************************************/
5 int funk(int n, int* n_1, int* n_2)
6 {
7 printf("funk(%d)\n", n);
8 if(n == 3){
9 *n_1 = 1;
10 *n_2 = 1;
11 return 2;
12 }
13 else{
14 int n_1_1, n_1_2;
15 *n_1 = funk(n-1, &n_1_1, &n_1_2);
16 *n_2 = n_1_1;
17 return *n_1 + *n_2 + n_1_2;
18 }
19 }
20 int func(int n)
21 {
22 int n_1, n_2;
23 return funk(n, &n_1, &n_2);
24 }
25 int main()
26 {
27 int n = func(10);
28 printf("n = %d\n", n);
29 getchar();
30 return 0;
31 }