包含while循环的递归函数的递归关系

Question

我有一个递归函数 int digit_sum(int number); returns 数字中所有数字的总和。例如，digit_sum(159) = 1 + 5 + 9 = 15.

函数如下：

int digit_sum(int n)
{
  if (n < 0)
    n = -n;

  if (n < 10)
    return n % 10;

  while (n % 10 == 0 && n > 0)
    n = n / 10;

  return n % 10 + digit_sum(n - (n % 10));
}

我不确定如何为这个函数编写递归关系。我知道 T(0) 是前两个 if 语句常量的总和。但是，对于 T(n)，我不确定如何表达 while 循环项和 T(n-k)。

modulo 操作员让我失望。这是一个猜测，我很确定这是错误的：

T(n) = c_1 + c_2 + c_3*n（while 循环）+ (n mod 10 + T(n - (n mod 10))) 对于 n >= 10

我知道整个 T(n-k) 项是错误的。

Answer 1

这是一个可能的解决方案：

#include <stdio.h>

int digit_sum(int n)
{
    if (n < 0)
        return digit_sum(-n);
    if (n < 10)
        return n;
    return (n % 10) + digit_sum(n / 10);
}

int main(int argc, char *argv[])
{
    printf("   9->%d\n", digit_sum(9));
    printf("  59->%d\n", digit_sum(59));
    printf(" 159->%d\n", digit_sum(159));
    printf("-159->%d\n", digit_sum(-159));
}

包含while循环的递归函数的递归关系

Recurrence relation of recursive function that contains while loop

c

recursion

recurrence

modulo

while-loop