c - 相互再帰の分析 - Luhn アルゴリズム

Question

Luhn アルゴリズム

クレジットカード番号の確認に使用

1. チェック ディジットである右端の数字から、左に移動して、2 桁ごとに値を 2 倍にします。この倍加演算の積が 9 より大きい場合 (例: 8 × 2 = 16)、積の桁を合計する (例: 16: 1 + 6 = 7、18: 1 + 8 = 9) か、または減算します。製品から 9 (例: 16: 16 - 9 = 7、18: 18 - 9 = 9)。
2. すべての桁の合計を取ります。
3. 合計モジュロ 10 が 0 に等しい場合 (合計が 0 で終わる場合)、数値は Luhn 式に従って有効です。それ以外の場合は無効です。

---

実装

#include<stdlib.h>
#include<stdio.h>
#include<stddef.h>

int luhnSum(int);

typedef struct{
  int quotient;
  int remainder;
}Tuple;

Tuple* split(int number){
  /* Split positive number into all but its last digit and its last digit */

  Tuple *tuple = malloc(sizeof(Tuple));
  tuple->quotient = number / 10;
  tuple->remainder = number % 10;
  return tuple;
}

int sumDigits(int number){
  /* Return the sum of digits of positive number n */

  Tuple *tuple = NULL;
  if(number < 10){
    return number;
  }else{
    tuple = split(number);
    return sumDigits(tuple->quotient) + tuple->remainder;
  }
}


int luhnSumDouble(int number){

  Tuple *tuple = split(number);
  int luhnDigit = sumDigits(2*(tuple->remainder));

  if(number < 10){
    return luhnDigit;
  }else{
   return luhnSum(tuple->quotient + luhnDigit);
  }
}

int luhnSum(int number){

  Tuple *tuple = NULL;
  if(number < 10){
    return number;
  }else{
    tuple = split(number);
    return luhnSumDouble(tuple->quotient) + tuple->remainder;
  }
}

int main(void){

}

---

相互再帰コードの空間と時間の複雑さを分析するには?