I think the rather simplistic approach would be: copy the whole WP_Widget_Categories from wp-includes/default-widgets.php, and paste it to your functions.php.
In there, you could modify the output by customizing this part of the class:
class WP_Widget_Recent_Posts extends WP_Widget {
...
<?php echo $before_widget; ?>
<?php if ( $title ) echo $before_title . $title . $after_title; ?>
<ul>
<?php while ($r->have_posts()) : $r->the_post(); ?>
<li><a href="https://wordpress.stackexchange.com/questions/70109/<?php the_permalink() ?>" title="<?php echo esc_attr(get_the_title() ? get_the_title() : get_the_ID()); ?>"><?php if ( get_the_title() ) the_title(); else the_ID(); ?></a></li>
<?php endwhile; ?>
</ul>
<?php echo $after_widget; ?>
...
}
I think there may be a better way to do this, but that’s the only way I know at the moment. :s