Transformer la récursivité en boucle

Maxim a écrit un algorithme récursif et a rencontré une exception Stack Overflow.







Pourquoi Maxim l'a-t-il fait?



Parce qu'il aime les solutions courtes et élégantes selon lui.







Il n'aime pas ça quand il écrit comme ça:







function factorial(n) {
  let res = 1;
  for (let i = 2; i <= n; i++) {
    res *= i;
  }
  return res;
}
      
      





Il veut écrire comme ceci:







const factorial = (n) => (n > 1 ? n * factorial(n - 1) : 1);
      
      





Mais quand il exécute des algorithmes récursifs comme celui-ci, il lui arrive de voir ceci:













Pourquoi l'algorithme "élégant" n'a-t-il pas fonctionné?



Javascript . factorial



. — . — 10700+ .







?



, .







, . , . .







, . , . . .







, .









, , , .







. , .







«TODO-»



, . , .







:







/**
 * factorial(n) returns n! for non-negative integer n
 * if n <= 18 it will be the exact value of the n!
 * if n <= 170 it will be approximate float value
 * if n >= 170 it will return Infinity
 */
function factorial(n) {
  if (n <= 1) return 1
  // TODO: Implement for non-trivial cases
      
      





.







«» , n <= 1



.







«» .







.







function factorial(n) {
  if (n <= 1) return 1;
  let result = 0;
  const todoStack = [];

  // TODO: Plan some tasks

  while (todoStack.length > 0) {
    const task = todoStack.pop();

    // TODO: process the task
  }

  return result;
}
      
      





while



. result



.







, .







N - 1



.







N - 1



N



.







todoStack



. , .







function factorial(n) {
  if (n <= 1) return 1;

  let result = 0;
  const todoStack = [];

  todoStack.push({ type: "multiplyBy", multiplier: n });
  todoStack.push({ type: "calculteFactorial", value: n - 1 });

  while (todoStack.length > 0) {
    const task = todoStack.pop();

    // TODO: process the task
  }

  return result;
}
      
      





, .







function factorial(n) {
  if (n <= 1) return 1;

  let result = 0;
  const todoStack = [];

  todoStack.push({ type: "multiplyBy", multiplier: n });
  todoStack.push({ type: "calculateFactorial", value: n - 1 });

  while (todoStack.length > 0) {
    const task = todoStack.pop();

    if (task.type === "multiplyBy") {
      const { multiplier } = task;
      result *= multiplier;
      continue;
    }

    if (task.type === "calculateFactorial") {
      const { value } = task;

      // «» 
      if (value <= 1) {
        result = 1;
        continue;
      }

      //  «»,   .
      todoStack.push({ type: "multiplyBy", multiplier: value });
      todoStack.push({ type: "calculateFactorial", value: value - 1 });
      continue;
    }
  }
  return result;
}
      
      





, for



. , «», , .









. , , . . , .







type Parser<T> = (
  input: string
) => Iterator<[parsedValue: T, restString: string]>;
      
      





many1



:







function many1<T>(parser: Parser<T>): Parser<T[]> {
  // TODO: Write this function
}
      
      





.







const helloParser = function* (text) {
  if (text.startsWith("hello")) {
    yield ["hello", text.slice("hello".length)];
  }
};

const many1HelloParser = many1(helloParser);

const parsed = [...many1HelloParser("hellohellohelloabc")];

/*
parsed = [
    [['hello', 'hello', 'hello'], 'abc'],
    [['hello', 'hello'], 'helloabc'],
    [['hello'], 'hellohelloabc'],
]
*/
      
      







, .







function many1(parser) {
  return function* (text) {
    //      
    yield* recMany1(parser, text, []);
  };
}

//   
// - 
// - ,     
// -   
function* recMany1(parser, text, parsedValues) {
  //            
  for (const [parsed, restString] of parser(text)) {
    const newParsedValues = [...parsedValues, parsed];
    yield* recMany1(parser, restString, newParsedValues);
  }

  //     -     
  if (parsedValues.length > 0) {
    yield [parsedValues, text];
  }
}
      
      







. .







:







function many1(parser) {
  return function* (text) {
    const tasksStack = [];

    tasksStack.push({
      type: "iterate",
      iterator: parser(text),
      parsedValues: [],
    });

    while (tasksStack.length > 0) {
      const task = tasksStack.pop();

      if (task.type === "yield") {
        //      -  
        yield [task.parsedValues, task.restString];
        continue;
      }

      if (task.type === "iterate") {
        //     
        //   
        const step = task.iterator.next();

        //    .    
        if (step.done) continue;

        //  
        const [parsedValue, restString] = step.value;

        //   :
        // 1.     restString
        // 2.     
        // 3.      

        // 3
        tasksStack.push({
          type: "yield",
          parsedValues: [...task.parsedValues, parsedValue],
          restString,
        });

        // 2
        tasksStack.push(task);

        // 1
        tasksStack.push({
          type: "iterate",
          iterator: parser(restString),
          parsedValues: [...task.parsedValues, parsedValue],
        });
      }
    }
  };
}
      
      





: , , .







:











, «» «» .







, . ? ? , ? ? , Stack Overflow Error?







. , ?









  1. , — .
  2. .



All Articles