遞歸添加數字

Question

我在LeetCode上遇到一個問題，需要對遞歸進行更新。這是問題：

Given a non-negative integer num, repeatedly add all its digits until 
the result has only one digit. 

For example: 

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, 
return it. 

我已經看到使用while循環的答案，但我想試試這與遞歸。 這是我到目前爲止有：

public int AddDigits(int num) { 
    if(num > 9) 
    { 
     num = (num%10) + (num/10); 
     AddDigits(num); 
    } 
    else{ 
     return num; 
    } 
} 

首先，我得到"Not all code paths return a value."但是基於if布爾檢查，應該不會這是好嗎？即使我else塊後添加return num，我仍然得到11.使用29的輸入，我的解決方案返回11，即使num最終成爲2.我上面的遞歸解決方案，該return num部分多次出現（我與測試Console.WriteLine語句） - 這是由於堆棧？

這是我想知道的內容 - 遞歸調用後爲什麼會發生的代碼 - 或者應該遞歸調用通常遞歸調用後，不包括代碼？

另外，我怎麼能得到這個遞歸和不使用while循環工作？

Answer 1

這是一個提示，不會產生正確的值，但它會讓你在那裏。

（另一個提示，你的函數需要兩個參數）

public int AddDigits(int num) { 
    if(num > 9) 
    { 
     num = (num%10) + (num/10); 
     return AddDigits(num); 
    } 
    else{ 
     return num; 
    } 
} 

編輯：解決方案在Python

def ra(n): 
    if n > 0: 
    return n % 10 + ra(n/10) 
    else: 
    return 0 

Answer 2

您需要在這兩個路徑的返回值（如果和其他人） 。

它可能是這（改變AddDigits(num);到return AddDigits(num);也可以（在其他的答案中給出），順便說一句，我不知道爲什麼，但它的工作原理）這樣

public int AddDigits(int num, bool root = true) { 
    if(num > 9) 
    { 
     var sum = num; 

     if(root) 
     { 
      while(sum > 9) 
      { 
       sum = AddDigits(sum/10, false) + sum%10; 
      } 
      return sum; 
     } 
     else return AddDigits(num/10, false) + num%10; 
    } 
    else{ 
     return num; 
    } 
} 

通話功能

var result = AddDigits(123456789); // ;) 

這是算法的工作原理。

 AddDigits(123456789) (root of call)   45 (45 is bigger than 9. AddDigits(45)  9 is not bigger than 9. return result. 
        ||        /\ repeat. while(sum > 9))  ||   /\ 
        \/        ||         \/   || 
    9 + AddDigits(12345678)       ||       4 + AddDigits(5)= 9  
        ||        || 
        \/      9+8+7+6+5+4+3+2+1 = 45 
9 + 8 + AddDigits(1234567)       || 
        ||        || 
        ....        ||   
        ||        || 
        \/        || 
      9+8+7+6+5+4+3+2+1 (now going back and summing them all) 

Answer 3

下面是使用LINQ的例子：

using System.Linq; 

static int Singularize(int val) 
{ 
    string str=val.ToString(); 
    int rslt=Enumerable.Range(0,str.Length).Select(i => str.Substring(i,1)).Select(int.Parse).Sum(); 
    return (rslt.ToString().Length==1) ? rslt : Singularize(rslt); 
} 

返回遞歸調用本身（在必要時）允許CLR離開當前呼叫轉移到遞歸調用和重複使用同一個堆棧的項目。如果您保留當前調用（通過使遞歸調用返回當前調用的結果），則遞歸鏈中的每個調用都會在駱駝（棧）上返回一個秸稈，直到駱駝破碎 - 即堆棧溢出錯誤。

Answer 4

所以真的是兩種不同的操作，都可以遞歸地陳述。

操作1是添加了一些共同的所有的數字：

int AddAllDigits(int n) 
{ 
    return n < 10 ? n : (n % 10 + AddAllDigits(n/10)); 
} 

操作2是保持執行操作1，直到我們只有一個單一的數字：所以現在

int ReduceToSingleDigit(int n) 
{ 
    return n < 10 ? n : ReduceToSingleDigit(AddAllDigits(n)); 
} 

我們可以

ReduceToSingleDigit(123456789); //gives 9 

現在，如果我們有可用的C＃6的優點，我們可以使我們的遞歸的樂趣通過將它們減少到表達式體而不是聲明體，它看起來更時尚一些（或者根據你的位置而混淆）。

int ReduceToSingleDigit(int n) => n < 10 ? n : ReduceToSingleDigit(AddDigits(n)); 

int AddDigits(int n) => n < 10 ? n : (n % 10 + AddDigits(n/10)); 

可愛。