递归 数的计算的简单理解

题目描述
我们要求找出具有下列性质数的个数(包含输入的自然数n):

先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:

不作任何处理;

在它的左边加上一个自然数,但该自然数不能超过原数的一半;

加上数后,继续按此规则进行处理,直到不能再加自然数为止.

输入格式
1个自然数n(n≤1000)

输出格式
1个整数，表示具有该性质数的个数。
输入输出样例 6 6
满足的数 6，16，26，126，36，136

这个题常规来想其实并不难，这是一个很简单的暴力递归
但题目要求是在1000之内， 暴力递归就会超时了
所以需要优化代码，这里采取记忆的方法（本人蒟蒻，请蒟蒻不要看到记忆二字退出）

#include <stdio.h>
#include <stdlib.h>
int f[1002]={0};         //定义全局数组并赋值为零，用来判断在递归的过程中有没有曾计算过的值  解释1： 
int num(int n)
    {
        f[1]=1;
    int i,sum=1;           //本身也可以所以sum从1开始
    if(n==1)
    {
        return f[n];
    }
    else
    {
        if(f[n]==0)        //判断曾经有没有出现过
        {
            for(i=1;i<=n/2;i++)
            {
                sum+=num(i);
            }
            return f[n]=sum;  //解释二：
        }

        else
            {
                return f[n];    
            }
        }
    }

int main()
{
    int n;
    scanf("%d",&n);
    printf("%d",num(n));
    return 0;
}

解释1；例如在计算num(4)时，会调用num(2)，这样如果重复递归很麻烦，如果num(2)在此前出现过，则将它记录下来，这样可以大大减少计算量。
解释2：注意这里面每次返回的都是f(n),f(n)无论怎样都曾经有过sum为其赋值。

关于递归，可能有些小伙伴不理解他是怎样运作的东西，你们其实可以用中文解释来思考，你们定义的函数究竟是一个干什么的函数，例如此题中的num函数，你要知道这个函数的作用是什么。num函数是一个求出输入n前面有多少种成立情况的函数，每次你遇到他时你就可以这么想他。

如果不能完全理解上面这段话，可以参照汉诺塔问题，在打印方法时，用的是同一种思想。