理解递归

发布于 2024-09-25 11:45:29 字数 478 浏览 3 评论 0原文

我正在努力理解动态编程示例中使用的递归。谁能解释一下它的工作原理。目标是找到具有一定价值的最少数量的硬币。

//对于所有面额 d，f(n) = 1 + min f(nd)

伪代码：

int memo[128]; //initialized to -1

int min_coin(int n)
{
   if(n < 0) return INF;
   if(n == 0) return 0;
   if(memo[n] != -1)

   int ans = INF;
   for(int i = 0; i < num_denomination; ++i)
   {
      ans = min(ans, min_coin(n - denominations[i]));
   }
   return memo[n] = ans+1; //when does this get called?

}

原文

I am struggling to understand this recursion used in the dynamic programming example. Can anyone explain the working of this. The objective is to find the least number of coins for a value.

//f(n) = 1 + min f(n-d) for all denomimations d

Pseudocode:

int memo[128]; //initialized to -1

int min_coin(int n)
{
   if(n < 0) return INF;
   if(n == 0) return 0;
   if(memo[n] != -1)

   int ans = INF;
   for(int i = 0; i < num_denomination; ++i)
   {
      ans = min(ans, min_coin(n - denominations[i]));
   }
   return memo[n] = ans+1; //when does this get called?

}

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

放低过去 2024-10-02 11:45:29

这个特定的例子在这篇文章中得到了很好的解释。顶级编码器。

基本上，这个递归是使用较小问题的解决方案（较小的n需要最少数量的硬币）找到整个问题的解决方案。动态编程方面是子问题的解决方案的记忆，这样它们就不会'每次都必须重新计算。

是的 - 正如他的评论中提到的，ring0 缺少 {} - 仅当子问题之前尚未解决时才应执行递归。

回复收藏 0 原文

娜些时光，永不杰束 2024-10-02 11:45:29

回答楼主的问题什么时候调用它？：在基于递归程序的解决方案中，相同的函数被自身调用......但最终返回......它什么时候返回？从函数停止调用自身开始，

f(a) {
  if (a > 0) f(a-1);
  display "x" 
}

f(5);

f(5) 将调用 f(4)，依次调用 f(3)、f(2)、f(2)、f(1)、f(0 ）。

f(0) 的 a 为 0，因此它不会调用 f()，并显示“x”，然后返回< /em>.它返回到之前的 f(1)，在调用 f(0) 后 - 完成 - 还显示“x”。 f(1) 结束，f(2) 显示“x”，...，直到 f(5)。你得到 6 个“x”。

To answer the owner's question when does this get called? : in a solution based on a recursive program, the same function is called by itself... but eventually returns... When does it return? from the time the function ceased to call itself

f(a) {
  if (a > 0) f(a-1);
  display "x" 
}

f(5);

f(5) would call f(4), in turns call f(3) that call f(2) which calls f(1) calling f(0).

f(0) has a being 0, so it does not call f(), and displays "x" then returns. It returns to the previous f(1) that, after calling f(0) - done - displays also "x". f(1) ends, f(2) displays "x", ... , until f(5). You get 6 "x".

回复收藏 0 原文

木有鱼丸 2024-10-02 11:45:29

换句话说，ring0 已经提到过 - 当程序到达基本情况并开始通过向上堆栈（调用帧）展开时。对于使用阶乘示例的类似情况，请参阅此。

#!/usr/bin/env  perl

use strict;
use IO::Handle;
use Carp qw(cluck);

STDOUT->autoflush(1);
STDERR->autoflush(1);

sub factorial {
    my $v = shift;

    dummy_func();
    return 1 if $v == 1;
    print "Variable v value: $v and it's address:", \$v, "\ncurrent sub factorial addr:", \&factorial, "\n","-"x40;
    return $v * factorial($v - 1);
}

sub dummy_func {
    cluck;
}

factorial(5);

In another terms from what ring0 has already mentioned - when the program reaches the base case and starts to unwind by going up the stack (call frames). For similar case using factorial example see this.

#!/usr/bin/env  perl

use strict;
use IO::Handle;
use Carp qw(cluck);

STDOUT->autoflush(1);
STDERR->autoflush(1);

sub factorial {
    my $v = shift;

    dummy_func();
    return 1 if $v == 1;
    print "Variable v value: $v and it's address:", \$v, "\ncurrent sub factorial addr:", \&factorial, "\n","-"x40;
    return $v * factorial($v - 1);
}

sub dummy_func {
    cluck;
}

factorial(5);

回复收藏 0 原文

~没有更多了~