插入成功后如何停止递归？

Question

问题定义是

Given an additional digit 0 ≤ x ≤ 9, write a function that returns the integer that results from inserting x in n, such that its digits also appear in ascending order from left to right. For instance, if n = 24667 and x = 5, the function should return 245667.

我的代码

// the divisions are integer division, no floating point
int x(int n, int insertValue)
{
    if (n == 0) return 0;
    int val = x(n/10, insertValue);
    if((n%10) > insertValue)
    {
        int q = insertValue * 10 + (n%10);
        return val * 100 + q;
    }
    return val*10 + (n%10);
}

例如x(2245,3)，则输出223435。但是我在处理224的时候已经处理完了。它不应该再继续添加要插入的值，我的意思是 3 不应该在 5 之前出现。

我可以想出一个解决方案，我可以在每个递归步骤中放入一个布尔标志，该标志通过取模 10 并除以 10 来达到个位数的情况。如果没有任何标识，则进入那个if块，否则不进入。但这听起来太傻了。

Answer 1

当你递归除法时，你实际上是从右到左，而不是从左到右，所以你应该检查一个数字是否比插入的数字小而不是更大（除非你总是让递归达到 n==0 条件并在你离开它的路上进行比较，但那将是无效的）。

第二件事是，一旦插入数字（正如我现在在问题标题中看到的那样，您已经知道这一点），您就不会破坏递归，因此它会在每个大于 [ 的数字之前重复插入=12=]。至于如何做到这一点：您已经在 if(n==0) 条件下停止递归，即如果 n==0 函数停止调用自身（它立即 returns ）。插入数字时的不同之处在于，您需要使用函数中的原始值 (n) 到 return，而不是进一步传递它。

此时它适用于您的示例，但如果您希望该函数正常工作，还需要考虑一种极端情况属性。当你没有什么可以除的时候 [if(n==0)] 你无论如何都需要插入你的数字 (return insertValue) 这样它就不会像在 x(2245,1) 调用中那样在左边丢失。

为简洁起见的改进：

% 与 * 和 / 具有相同的优先级，因此此处不需要括号。
我删除了 val 变量，因为它现在只使用了一次，并不总是需要计算。

这是工作代码：

int x(int n, int insertValue){
    if(n == 0) return insertValue;
    
    //if insertion point was found, use original value (n)
    if(n%10 <= insertValue)
        return n*10 + insertValue;

    //if not there yet, keep calling x()
    return x(n/10, insertValue)*10 + n%10;
}

插入成功后如何停止递归？

How can I stop recursion after I succeed my insertion?

algorithm

function

recursion

recurrence